#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 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 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 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