Home > Theory Of Computation > DFA Example : Construct The Minimal Finite Automata All The Strings Of a & b Where Second Symbol From Right End Is a

DFA Example : Construct The Minimal Finite Automata All The Strings Of a & b Where Second Symbol From Right End Is a

Construct The Minimal Finite Automata All The Strings Of a & b Where Second Symbol From Right End Is a

Solution 

In This Problem, The Second Symbol From Right ‘a’

 

You Can Easily Solve Problems If The Question Is Asked Fixed Left Side Symbol.

If They Ask You Fixed Right Side Symbol You Have To Use Formula.

Σ={a,b} // Given Strings Accepts a & b.

Example – aabbab

Computer Reads One By One Character From Left

a

b

b

a

b

 

// Computer Don’t Know The No.Of Symbols Comes After In The Language.

Computer Reads aabbab One By Character And Computer Don’t Know The No.Of Character Are There After The First Character.

And Computer Don’t Know The Reading Character Count (Wheather It Is Second Or Third Of Fifth From The Right Side End)

 

Left Hand Side ” Problems ” Are Easy Because The Computer Reads One By One Character And Knows The Exact Point Of The Character But In Right Hand Side Computer Don’t Know.

If You Draw Directly DFA.

For Right Hand Side Fixed Symbol, It Is Too Logical.It Takes Lot Of Time And Space, There Are Lot Of Chances Of Getting Wrong Diagram.

 

” SIMPLE TECHNIQUE FOR RIGHT-HAND SIDE FIXED SYMBOL PROBLEMS TO GET DIRECTLY MINIMAL DFA ”

 

In This Problem We Are Directly Getting NOS, We Are Not Getting DFA.

 

Given

nth Symbol From Right Side In My DFA I’ll Get 2States // Where ” n ” Is nth Symbol From Right, 2=a,b Are Input Symbols.

Because Problem Said Is 2nd Symbol, i.e n=2.

If Problem is 3rd From Right n=3

If Problem Is 4th From Right

n=4

 

2n–> States (22=4) // 2=a,b are input symbols Σ={a,b}

2n-1

–> Final States(22-1=2)

Total States=4

Final States=2

Total States – 1 = Final States

 

For This Type Of Problems, We Have To Draw Transition Table.

It Is Important To Draw Transition Table For This Type Of Problems.

 

Transition Table

If A Symbol Is Fixed From Right, You Have To Enter Odd Number In The Transition Table.

Now Using This Transition Table I’ll Draw Minimal DFA.

Remember

IF QUESTION ASKED FOR RIGHT END.

  1. NOS –> 2n(22=4) // 2=Input Alphabets, n=2(2nd Symbol)
  2. NOFS –> 2n-1(22-1=2)
  3. TRANSITION TABLE
  4. USING TRANSITION TABLE DRAW DFA

 

 

 

 

 

 

One thought on “DFA Example : Construct The Minimal Finite Automata All The Strings Of a & b Where Second Symbol From Right End Is a

Leave a Reply