Home > Finite Automata in theory of computation

Conversion Of E-NFA To NFA – Theory Of Computation

Conversion Of E-NFA To NFA - Theory Of Computation Example-1 ε-Closure (q0) - {q0,q1} ε-Closure (q1) - {q1} ε-Closure (q2) - {q2} ε-Closure (q3) - {q3,q1q2} 1)  Initial State - q0 2) Construction Of δ1 Note:- When We Convert ε-NFA To NFA, There Will Be No Change In Number Of States. This Is The Resultant Diagram. There Is No-Transition With 'ε"(Epsilon)

Read More

Conversion Of E-NFA To NFA – Finite Automata –

Conversion Of E-NFA To NFA - Finite Automata The Process Of Conversion Of ε-NFA To NFA Is Called As Thomson Construction. Note:- No Change In Initial State No Change In The Total No. Of States May Be Change In Final States Algorithm Let M=(Q,Σ,δ,q0,F) - ε-NFA M1= (Q1,Σ,δ1,q01,F1) - NFA 1) Initial State q01=q0 2) Construction Of δ1 δ1 (q,x)=ε-Closure(δ(ε-Closure(q),x) 3) Final State Every State Who's ε-Closure

Read More

NFA To DFA Conversion In Theory Of Computation

NFA To DFA Conversion In Theory Of Computation Construct The DFA For The Following NFA     DFA Using DFA Transition Table If All States Are Final The Minimal DFA Will Be My Initial State Will Be My Final State And This Is The DFA.   Example-2 Conversion Of NFA To DFA Find The Minimal No Of States In NFA Solution:- Transition

Read More

DFA Example : 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

Read More

Compound Automata (DFA Example): 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

Read More

Compound Automata(DFA Example): Construct The Minimal Finite Automata That Accept All The String Of a & b Such That There Is One ‘a’ Or One ‘b’

Construct The Minimal Finite Automata That Accept All The String Of a & b Such That i) There Is One 'a' Or One 'b'   Solution:- Compound Automata Means Combining Two Automata's (Machines) Which Becomes One Automata(Machine). Let's Know Why We Should Combine Two Automata. If The Question Contains More Than One Condition ' I Have Solved

Read More

Construct The Minimal Finite Automata And Find The Number Of States In Following Language

Construct The Minimal Finite Automata And Find The Number Of States In Following Language L={ambn/m≥0,n≥2018}   This Is A Interesting Problem. Given m≥0 n≥2018 // 2018 Is A Big Number, It Becomes Very Big DFA But We Need Minimal DFA. Σ={a,b} m≥0 Let n≥1 So My Language Is L={b,bb,bbb,bbbb.......} // ε Epsilon Is Not There Because m=0,n=0,n=1 means 'b'   i)   ii) m≥0,n≥2 So

Read More

DFA Example : Construct The Minimal Finite Automata And Find Number Of States In The Following

Construct The Minimal Finite Automata And Find Number Of States In The Following i) L={ambn/m,n≥0} Patter Question a=input symbol b=input symbol m&n≥0 So My Language Is L={ε,a,b,ab,aab,aaab,aaabbb......} // Infinite String   Explanation Of Language m,n Can Be '0' (zero) m can be '1' or '2' or '3'...... n can be '1' or '2' or '3'....... If m,n is '0'(zero) then a0b0  Becomes (0), Means ε(Epsilon) If

Read More

DFA Example : 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

Read More

DFA Example : Construct Minimal Finite Automata That Accepts All Strings Of 0’s & 1’s Such That a) |w|≅0 (mod 2), b) |w|≅1 (mod 2), c) |w|≅2 (mod 3)

Construct Minimal Finite Automata That Accepts All Strings Of 0's & 1's Such That a) |w|≅0 (mod 2), b) |w|≅1 (mod 2), c) |w|≅2 (mod 3) |w|= Length Of 'w' String a) |w|≅0 (mod 2) Means If I Divide Length Of String With '2' I Should Get Remainder '1' 'ε' Is Length '0' String,

Read More