The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
2.6k views

Let $L$ be the set of all binary strings whose last two symbols are the same. The number of states in the minimal state deterministic finite state automaton accepting $L$ is 

  1. $2$
  2. $5$
  3. $8$
  4. $3$
asked in Theory of Computation by Veteran (59.6k points)
edited by | 2.6k views
0

Praveen Saini  sir I made NFA with 5 states in my NFA 2 final states One fo aa other for bb ,still I am gwtting 5 states .can we say both are correct

@arjun sir 

3 Answers

+31 votes
Best answer

Binary strings whose last two symbols are same .

Regular expression $= (0+1)*(00+11) $

Having $NFA$

Equivalent $DFA$

Total no of states $= 5$ 

answered by Veteran (55k points)
edited by
+1

@Arjun Sir, please help me, what is the problem with this diagram. It may be stupid question but I'M stuck.

+1
@thepeeyoosh

epsilon will not be a part of this language.
0
is there any systematic to solve these kind of questions some times we may miss out some states while conversion ?
0
It may sound stupid but I am stuck.

In the above min DFA, for q1 and q2- transitions on i/p 0/1 are going to final/non-final states respectively. Also  for q3 and q4- transitions on i/p 0/1 are going to non-final/final states respectively. Then why cant we merge them as per definition of equivalence classes, making min DFA of 3 states(which turned out to be wrong).

Please explain, Whether my understanding of equivalence classes is wrong or what?
+2

"for q1 and q2- transitions on i/p 0/1 are going to final/non-final states respectively. Also  for q3 and q4- transitions on i/p 0/1 are going to non-final/final states respectively. Then why cant we merge them"

because q1 is a non-final state and q2 is a final state. they can never be equivalent.

similar with q3 and q4.

0
Sir i made the same dfa but made q0 as final state too thinking that Null is also accepted. Sir how should I decide for epsilon in this as well as similar types of questions??
+1

it depend on the language.

set of symbols are {0,1} , last two symbols must be same , last two symbols in any string will be either 00 or 11 .

i.e .. (anything) (00+11)

regular expression =(0+1)*(00+11)

0

Praveen Saini  sir I made NFA with 5 states in my NFA 2 final states One fo aa other for bb ,still I am gwtting 5 states .can we say both are correct

@arjun sir 

0
I hope  you are right
0
Is 000 belongs to this language?If so it is not accepted
+2 votes
I made a fsm with 5 states .here the strings ending in 00 or 11 are to be accepted..just make 2 separate fsm and join them
answered by Boss (14.3k points)
0
Can you please post a picture how you'd JOIN those 2 FA?
+1
Joining of two FA will be same as Praveen sir's answer .
0
nt a gd way of explaining things ....
0 votes

Please Let me know if this is the right answer as in this case also its 5 states but diagram is different.

answered ago by (295 points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

41,055 questions
47,653 answers
147,217 comments
62,380 users