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.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.3k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,861 questions

47,532 answers

145,984 comments

62,293 users