The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes

asked in Theory of Computation by Junior (637 points) | 64 views

2 Answers

+1 vote

I think total no. Of states should be 4 ,check it if i done wrong somewhere please help me,

answered by Active (3.9k points)
edited by
here,  ⋋ is denoting empty string. is it true? no where in the question he mentione it.
Some books (peter linz) denoted by $\lambda$ or some books denoted by $\epsilon$ ,it is by default.
I think u did some mistake

See the question there is a

Transition from q3 to q0 on a

And u didn't show it in your solution
Yeah ,u are right ,I will correct that.thanks
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
answered by Active (2.4k points)
edited by
Answer is 6
i am not getting how the answer is 6?

i repeatedly did the question but again and again i am getting 9 only....

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

36,157 questions
43,608 answers
42,860 users