The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
2.9k 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.7k points)
edited by | 2.9k 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 

0
Yes. we are getting 5 states. Can anyone tell which is the correct answer?

3 Answers

+32 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 (55.4k 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
0

is there any systematic to solve these kind of questions some times we may miss out some states while conversion ?

Method 1: Write the language in ascending order of size (enumeration of kleene closure) but don't miss out/include any term according to condtion given in question. Once you are done with the language, draw DFA for accepting smallest string and while making transitions from each state just think what each state has seen and make appropriate transitions.

Method 2 : NFA -> DFA -> minimize it

Method 1 is easy once you practice it.

+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.4k 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 by Junior (933 points)
Answer:

Related questions



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

44,297 questions
49,786 answers
164,383 comments
65,857 users