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.5k
- Digital Logic 2.1k
- Programming & DS 4k
- 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 450
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,106 questions

45,610 answers

132,248 comments

49,238 users