Home > Theory Of Computation > DFA Example : Consider The Following DFA And Find Out How Many Strings It Accepts

DFA Example : Consider The Following DFA And Find Out How Many Strings It Accepts

Consider The Following DFA And Find Out How Many Strings It Accepts

Solution:- 

TOTAL Given – 7 States

From Starting State q0 I’ll Go To qIf I Get 0 Or 1

From q1 I’ll Go To q2 If I Get 0 Or 1

From q2 I’ll Go To q3 If I Get 0 Or 1

From q3 I’ll Go To q4 If I Get 0 Or 1

From q4 I’ll Go To q5 If I Get 0 Or 1

qIs Not My Final State

qIs My Final State

qTo qAll Are My Final States qIs Not

My Maximum Length Of The String Is 5(q0To q5) _ _ _ _ _

 

Five Length String Are Accepted After ‘5’ It Is Going To Non-Final State

Non-Final State Means Strings Are Not Accepts So My Maximum Length Of A String Is ‘5’

 

My Maximum Length Of The String Is ‘ε’ (Epsilon) Because My Initial State Is My Final State.

 

If My Initial State Is My Final State Then ‘ε’ ( Epsilon) Is Accepted.

 

I HAVE TO SEE THE NO. OF STATES & THE NO. OF STRINGS ACCEPTED.

Even If I Dont Give Any Input, My String Is Going To Final State And Accepted (ε) Epsilon Is Accepted.

2// 0 (Zero) Is I’m Not Giving Any Input Alphabets, 2 Is Input Alphabets(0,1)

20=1

 

Next Is ‘q1

q1

Accepts ‘1’ String Itself And ‘0’ Which Came From ‘q0

0,1 Are Accepted.

20+ 21

Next

20+ 21+22

Next

20+ 21+22+23

Next

20+ 21+22+23+24

Next

20+ 21+22+23+24+25

=1+2+4+8+16+32

=7+24+32

=63

 

63 States Are Accepted.

 

 

One thought on “DFA Example : Consider The Following DFA And Find Out How Many Strings It Accepts

Leave a Reply