#FiniteAutomataapplications

[smartcherryposts]

Complement Of Finite Automata

Complement Of Finite Automata Means The Finite Automata Which Is Obtained By Interchanging Final And Non-Final States Is Known As Complement Of Finite Automata.

In This Concept, I'll Change Final States To Non-Final To Final State And Final To Non-Final State. By Doing This The Language Changes. M-Automata(DFA) L-Language M Supports L Language   The String Which Comes In Language L Are Accepted By Machine M L⊆Σ* L Belongs To Sigma Star Σ* Means Universal Set Of Strings(All The Strings) L⊆Σ* Means The Strings Which Are Accepted By Language Comes Under 'L' Not All Strings Comes Under 'L'   M→L⊆Σ* Means Machine M Accepts Strings Which Are Belongs To 'L' And L Is The Language(Set Of Strings) Which Are Subset Of Universal Set Of Strings i.e Σ* (Sigma Star)

Then What Is Complement Of Finite Automata?

If I Give Complement For Machine 'M' That Becomes M1 M1→L1= Σ*- L M1 Is The Machine Which Accepts The Language L1 L1= Σ*- L   This Machine M1 Accepts The Language L1 And L1  Is Universal Set Of Strings Language. M→L⊆Σ* M1→L1= Σ*- L   I Hope You Understood The Difference Between Machine M And Machine M1 Example

Σ={a,b}

L=String Starts With 'a'

This Is (M) Machine Example.  

     2. Σ={a,b}

L=String Does Not Start With 'a'  

This Is M1 (Machine Complement) Example In M1 The Non-Final States Becomes Final State Including Dead State And Final States Becomes Non-Final State.   Cross-Check baa  

Remember

L(FA)∩l(FA1)=Φ L(FA)∪(FA1)=Σ* M→n states k final states M1→ n states n-k final states       Read the full article

[smartcherryposts]

Construct The Minimum Finite Automata That Accept All The Strings Of a & b Such That String Contains At least 2 a's & ηb|w|≅0mod3

Construct The Minimum Finite Automata That Accept All The Strings Of a & b Such That

i) String Contains At least 2 a's & ηb|w|≅0mod3

Solution:- (Check Previous Two Problems For Better Understanding) CONDITION GIVEN:- String Should Contain At least 2 a's And ηb|w|≅0mod3(Means No Of b's In String Is Approximately Equal To O Mod 3(If I Divide The No.Of b's With 3, I Should Get Remainder As 0)  

FINITE Automata 1:-

Σ={a,b} L={aa,aaa,aaaa,aaaaa....}

FINITE AUTOMATA 2:-

ηb|w|≅0mod3 Means No Of b's In String Is Approximately Equal To O Mod 3(If I Divide The No.Of b's With 3, I Should Get Remainder As 0

Possible Remainders For 3 Are 0,1,2   Mean If I Divide No. Of b's In A String With 3 I Should Get Remainder As 0   Imagine-{b,bbb,babbab,bbabbbbba....} If No Of b's Are '0' In A String And If I Divide 3 With 0 I'll Get Remainder '0'   0 Is Divisible By 3 0 Means ε Means L={ε,1,2,3}={ε,b,bb,bbbb...}

CROSS PRODUCT FINITE AUTOMATA 1 × FINITE AUTOMATA 2 => {(q0,q3),(q0,q4),(q0,q5), (q1,q3),(q1,q4),(q1,q5), (q2,q3),(q2,q4),(q2,q5)}  

FINITE AUTOMATA

FINAL STATE Is q2,q3  Because Two Conditions Should Satisfy. CROSS CHECK babab // aa,bbb Read the full article

[smartcherryposts]

Construct The Minimal Finite Automata That Accept All The String Of a & b Such That There Is Even No. Of a And Even Number Of b

Construct The Minimal Finite Automata That Accept All The String Of a & b Such That i) There Is Even No. Of a And Even Number Of b   Solution:- Question Is Final Automata Should Contain Even Number Of 'a's And Even Number Of 'b's Even Numbers Are 0,2,4,6,8,.....  

CREATE TWO SEPARATE AUTOMATAS WITH GIVEN TWO CONDITIONS

Finite Automata 1:- Even Number Of 'a's Σ={a,b}

q0 Is My Initial And Final State Because Of ε q0 Goes To q1 And q1 Goes To q0(aa) I Dont Bother About Number Of b's On q0q1 Finite Automata 2:- Even Number Of b's(ε,bb,bbbb,bbbbbb....)

I Have Drawn Finite Automata 2 Using The Same Procedure Used In Finite Automata 1.   Now Cross Product (Or) Cross Multiplication Finite Automata 1 × Finite Automata 2

=> {(q0,q2),(q0,q3) (q1,q2),(q1,q3)}  NOS - 4   Now DRAW FINAL DFA Using These States By Observing Finite Automata 1 And Finite Automata 2

Final State Will Be The Combination Of Finite Automata 1 And Finite Automata 2 Only. Because The Condition Given Is Two Conditions Should Be Satisfied. No Of Even 'a's And No. Of Even b's In A String.   Cross Check abaaba

Check Previous Problem For Better Understanding     Read the full article

[smartcherryposts]

Construct Minimal Deterministic Finite Automata (DFA) Start And End With Different Symbol

Construct Minimal Deterministic Finite Automata (DFA) Start And End With Different Symbol Where Σ={a,b}   Condition Given Is If Your String Is Starting With 'a' It Should End With 'b' If Your String Is Starting With 'b' Then It Should End With 'a'   L={ab,ba,abbb,abab,baba,bbaa.........} // Infinite Language

  Read the full article

[smartcherryposts]

Construct The Minimal Finite Automata That Accepts All Base 8 Numbers Which Are Divisible By '6'

Construct The Minimal Finite Automata That Accepts All Base 8 Numbers Which Are Divisible By '6' (Binary Means Base 2, i.e Σ(0,1) Input Symbols Will Be 2 Only 0 & 1) (Integer Means Base 10,i.e (0,1,2,3,4,5,6,7,8,9) Input Symbols Will Be 10 Only 0&1&2&3&4&5&6&7&8&9)   Here Given Input Symbols Are Base '8', It Means OCTAT. My Input Symbols Are Σ={0,1,2,3,4,5,6,7}   Example :- (22)8 = (2×81+2×80)10 =(16+2)10 =(18)   After Conversion Into Decimal (22)8 Is Divisible By '6' Possible Remainders For '6'

Question Is Divisible By '6' Means Remainder Should Be '0' For '0' We Gave 'q0'As State ,  'q0' Is Final State.  

q1= q4 q2=q5   q1& q4 Are Same, I'll Merge Both. q1= q4 q2 & q5  Are Same, I'll Merge Both. q2=q5  

No Commons States In This Table. MAKE DFA USING THIS TABLE.

DFA Is Ready. Now Take Any Number Which Has Base 8, Which Is Divisible By '6' Example:- (22)8 If I Give '2' To 'q0' , I'll Go To 'q2' If I Give '2' To 'q2', I'll Go To 'q0'(Final State) Hence Satisfied.   TYPES OF PROBLEMS WE SOLVED TILL NOW. BINARY(INPUT SYMBOL) - (0,1) INTEGER (INPUT SYMBOL) - (0,9) BASE 8, OCTAT (INPUT SYMBOL) - (0-7) Read the full article

[smartcherryposts]

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  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 2n States // 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. NOS --> 2n(22=4) // 2=Input Alphabets, n=2(2nd Symbol) NOFS --> 2n-1(22-1=2) TRANSITION TABLE USING TRANSITION TABLE DRAW DFA             Read the full article

[smartcherryposts]

Construct Minimal Deterministic Finite Automata Ends With aa Or Ends With bb

Construct Minimal Deterministic Finite Automata Ends With aa Or Ends With bb Condition Given Is The String Must End With aa Or Can End End With bb. L={aa,bb,aaa,bbb,abaa,babb} // Infinite String   Lets's Create NFA (Smallest String Is 'aa' Or 'bb')

DFA

Remember

Dead State Concept Will Not Comes In The 'End With ' Problems. If I Get 'a' Of 'q2', I'll Put Self Loop Because, It Doesn't Matter If I Get Any Number Of a's After q1(a), I'm Ending With 'aa' That's It. If I Get 'b' On 'q4' I'll Put Self Loop Because It Doesn't Matter If I Get Any Number Of b's After 'q3'(b), I'm Ending bb, That's It. If I Get 'b' On My Final State 'q2', ill Send To 'q3' (Non-Final State) So That It End's 'bb' If I Get 'a' On My Final State 'q4' I'll Send It To 'q1', So That It Ends With 'aa'. In This Case, I Can't Merge Both The Final States 'q2' and 'q4' Because Final States Are Different For Both The Two Possible Strings.   Read the full article

[smartcherryposts]

Construct Deterministic Finite Automata (DFA) Start And End With Same Symbol

Construct Minimal Deterministic Finite Automata9DFA) Start & End With Same Symbol Where Σ={a,b}   Conditions - If Your String Is Starting With 'a', It Should End With 'a' Only. If Your String Is Starting With 'b', It Should End With 'b' Only.   " 'Dead State' Concept Comes When I Say About Start Or End Symbol Or When I Say About 'Substring'.   Language Set L={a,b,aa,bb,aba,bab,abba,.......} // a is the smallest string and starts & ends with 'a' (same symbol)   Let's Create Automata For Small String 'a' So That We Convert This NFA(a) To DFA(a)   L={a,b,aa,bb,aba,bab,abba,.......}   String a & b

String a String b, String aa, String bb.....

String aba,bab,abba

  NOS=5 // Number Of Strings = 5       Read the full article

[smartcherryposts]

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

q0 And At Last Came To q0 And 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 ' q1 ', 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.     Read the full article