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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+20 votes

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

- $2$
- $5$
- $8$
- $3$

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

+36 votes

Best answer

+1

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

0

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

+1

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?

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?

+3

*"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

+1

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.

+3 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

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 559
- Exam Queries 555
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,932 questions

52,335 answers

182,384 comments

67,817 users