Home > Theory Of Computation > String Start With | End With | Contains : Finite Automata Example

String Start With | End With | Contains : Finite Automata Example

We Will Understand How The Problems Ar Designed On Finite Automata And How These Problems Are Solved.

 

I’ll Design Problem And I’ll Show You Three Variations Of The Problem And I’ll Show You How Finite Automata Changes With ” Small Changes”.

First Point For You Is, You Have To Read The Problem And You Have To Understand The Problem & Know What That Problem Is.

And You Have To Take A Decision To Draw Its FA(Diagram)

 

Let’s Understand Problems, This Is How Problems Looks Like.

 

Construct A Finite Automata, Over The Input Alphabet(a,b) Where The String Starts With a.

 

a) Σ(a,b)

String Starts With a.

L={a,ab,aa,abb,abaa…..}

FA

 

Checking Wheather This Is Correct (or) Wrong.

I’ll Take A String ‘abab’

‘abab Is A Valid String, It Starts With ‘a’.So Definitely I Should Accept ‘abab’

First I’ll Start With ‘a’ From ‘abab’

-> (Machine) I’m Starting From q0, I’ll Give ‘a’ to ‘q0‘ ,

By Giving ‘a’ To ‘ q0‘ , I’m Moving To ‘q1‘, Now My Pointer Is On ‘q1

abab

 

-> Now I’m(Machine) Giving ‘b’ To ‘q1‘, My Pointer Will Be On ‘q1‘Only

abab

 

-> I’m Giving ‘a’ To ‘q1‘, The Pointer Again Will Be On ‘q1

abab

 

-> I’m Giving ‘b’ To ‘q1‘ , The  Pointer Comes To ‘q1‘ Only Again

abab

 

-> If My String (abab) Is Over And The Pointer Still Be On ‘q1‘ State.

So, Definitely String(abab) Is Valid

abab

 

And I’ll(Machine) Accept This String.

 

-> This Is How We Have To Solve The ‘Starts With a‘ Problem.

 

Next Problem Is

b) End With ‘a’

-> Here I(Machine) Shouldn’t See Starting Of The String.

-> I Have To See Wheather String Is Ending With ‘a’ Or ‘not’.

-> This Problem Is Different From Previous Problem Lets See What Is The Difference.

-> Starts With ‘a’

Σ=(a,b)

L={a,ba,aa,baba…} // I Can Create Infinite Strings Which Ends With ‘a’

-> First We Have To See The Smallest String In The Language.

We Should See The String Which Has Small Length.

-> And I Have To Try To Create Automata Which Accepts That String , So That It Should Be Optimized Automata.

 

-> I’ll Tell You How To Optimize Automata In Upcoming Topics Of Theory Of Computation.

 

-> Remember Whenever You Want To Draw Automata, You Have To Draw Automata For The Smallest

String In The Language

L={a,ba,aa,baba….} // a is The Smallest String

Then We Can Convert That Automata For Other Strings.

 

->Smallest String Is ‘a’

I’m(Machine) Giving ‘a’ As Input To The Starting State ‘q0

And I’m Making ‘q1‘ To Accept The String ‘a’

 

-> If String Is Ending With ‘a’ I’ll(Machine) Stop.

XXXa

 

-> Before ‘a’ There Can Be Anything Like ‘b’ There Can Be Any Number Of ‘b’s Before ‘a’

 

-> I(Machine) Dont Need To Count The Number Of Alphabet Coming Before ‘a’

 

-> If String Is Ending With ‘a’ I ( Machine) Will Accept Thats It.

 

-> That’s Why ‘b’ Of ‘q0‘ Is Self Loop.

-> Because I Dont Need To Know About The Number Of ‘b’ Coming Before ‘a’ , I Dont Want Also My String Should End With ‘a’ That’s It.

-> If String Is Like This bbba

 

then

qAnd At Last Came To qAnd Ended At ‘q1‘ With ‘a’

-> ‘q1‘ Accepts ‘a’

Thats Why I(Machine) Gave Self Loop For ‘b’

 

 

Now

Till Now We Came To Know About Smallest String ‘a’ And Which Ends With ‘a’

-> What If The String Is Like This ‘ baba ‘

 

First Thing Computer Do Is.

Computer Reads One By One Charecter ‘b’,’a’,’b’,’a’  Like This

 

-> Thats Why Whenever I Get ‘a’ I’ll Go To Final State.

 

-> baba

But At The End If I Get ‘b’

-> Why Because If I(Machine) Go To Dead State, I(Machine) Cant Come Back To The Machine(State)

 

-> baba

If I’m Getting ‘a’ After b, My String Goes To Dead State Only, I Cant Come Back Again.

-> baba

Lets See How We(Machine) Will Accept This String.

 

-> First

I Gave ‘a’ As Input ‘q0 ‘ And I Reached Final State ‘q1

-> What If I Get ‘a’ Again After ‘a’,

 

->I’ll Be On Final State ‘q1‘  Only String Ends With ‘a’ Only Like Below Picture

-> If I Get Any Number Of a’s After ‘a’ , I’ll Be On ‘q1‘ Only Because Of Self Loop.

 

-> If ‘b’ Comes As Input On ‘q1‘ Then

I Should Restart Machine.

I Should Start Machine Again.

 

To Check Wheather I’m Getting ‘a’ In The Final State (or) Not

That’s Why Pointer From ‘q1‘ Goes To ‘q0‘ (Initial State)

 

-> If I Get ‘a’ , I Should Restart The Machine Then I’ll See For ‘a’ Wheather It Is On Final State Or Not.

 

-> Moving ‘q1‘ To ‘q0‘ Is Important.

 

I’ll Explain With Example

STRING – ababba(Valid String)

 

How Machine Works

-> Given Input ‘a’ To ‘q0‘ , Pointer Moves To ‘q1

 

-> I Got ‘b’ Now, I Gave Input ‘b’ To ‘q1‘, Pointer Moves To ‘q0

 

-> I Gave ‘a’ To ‘ q0‘ , Pointer Moved To ‘q1

 

-> I Gave ‘b’ To ‘q1‘ , Pointer Moves To ‘q0

 

-> I Gave ‘b’ To ‘q0‘ Pointer Moves To ‘q0‘ Only

 

-> I Gave ‘a’ To ‘q0‘, Pointer Moves To ‘q1

At The End Of The String My Pointer Is On ‘q1‘.

If My Pointer Shows ‘q1‘ At The End It Means It Is Valid String.

 

-> We Already Know String Which Ends With ‘a’ Is Valid, Now We Have Shown It Finite Automata.

 

-> String Satisfies This Language And Finite Automata Is Correct.

 

Let’s Write Tuples For The Above String 

(Q,Σ,δ,q0,F)

Q=(q0, q1)

Σ=(a,b)

δ=(QXΣ->Q)

q0= {q0}

F={q1}

 

 

δ=(QXΣ->Q)

δ(q0,a)->q1

δ(q1,b)->q0

δ(q0,b)->q0

δ(q0,a)->q1

All These Are Called As ID.

 

 

(C) Contain ‘a’

-> String Should Contain ‘a’ At Starting Or Middle(or) At The End Anywhere In The String.

L={a,ba,bab,aba,bbab……} \\ Infinite String Language

Σ={a,b}

Finite Auomata For Small String ‘a’

 

-> What If String Has ‘b’ Before ‘a’ ‘ba’

I’ll Put Self Loop To ‘ q0 ‘

 

If I Give Self Loop To q0

 

It Doesn’t Matter The Number b’s Comes Before ‘a’

 

 

-> What If I Get ‘a’ Or ‘b’ After I Getting ‘a’ For Once.

Like This

bbb a bbbaaaba

I’ll Accept All Theb’s And a’s Which Comes After ‘a’

 

-> Here Point Is Once I Get ‘a’ And Reach Final State, My Given Condition Is Satisfied.

-> It Doesn’t Matter Whatever Comes After ‘a’ But I’ll Accept I’ll Not Reject.

 

-> Thats Why At ‘ q‘, I’ll Put Self Loop Of a,b

Like This

Before I Dont Need To Count About The a’s & b’s Which Are Coming After ‘a’

If I Dont Need To Count, I Can Give Self Loop For Those

Because In Looping I Cant Count.

 

-> If There Is A Need Of Counting I Need To Give Transition For That.

-> Where There Is No Need Of Counting At That Point, I’ll Give Self Loop.

 

 

Leave a Reply