The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+1 vote

0 votes

Given is NFA first convert it into DFA then convert into Minimal DFA...

By converting NFA to DFA we get 9 ( = 8+1 DS) states and every state is unique therefore DFA is Minimal ===> no.of states in minimal DFA is 9.

the states in DFA are

⋋ a b

*****q0 q1 q1 q2

******q1 - - q1q3

q2 q3 - -

******q1q3 - q0q3 q1q2q3

q3 - q0q3 q2

q0q3 q1 q0q1q3 q2

******q1q2q3 q3 q0q3 q1q2q3

******q0q1q3 q1 q0q1q3 q1q2q3

add Dead State as one more state and - in the transition leads to Dead state

By state equivalence theorem all are unique states....

*** is intial state and ** are final states **

`note that ⋋ considered as input symbol not empty string`

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 486
- Exam Queries 435
- Tier 1 Placement Questions 18
- Job Queries 56
- Projects 9

36,157 questions

43,608 answers

123,961 comments

42,860 users