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

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

+30 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 ?

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?

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?

+1

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

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.9k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 447
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

37,939 questions

45,453 answers

131,190 comments

48,206 users