Introduction

• Automata Introduction

DFA

• DFA Introduction

DFA Examples

• DFA which accepts strings of odd length
• Design a DFA over w ∈ {a,b}^* such that No of a = 2 and there is no restriction over length of b
• DFA for No of a(w) mod 2 = 0 and No of b(w) mod 2 = 0
• DFA for No of a(w) mod 2 = 0 or No of b(w) mod 2 = 0
• DFA for No of a(w) mod 2 != 0 and No of b(w) mod 2 != 0
• DFA for No of a(w) mod 3= 0 and No of b(w) mod 3= 0
• DFA for No of a(w) mod 3 > No of b(w) mod 3
• DFA for binary No divisible by 2
• DFA for binary No divisible by 3
• set of all strings can be accepted which start with 'a'
• Set of all strings can be accepted which contains ‘a’
• Set of all strings can be accepted which end with ‘a’
• Set of all strings can be accepted which start with ab
• Set of all strings can be accepted which contain ab
• Set of all strings can be accepted which ends with ab
• Start and end symbol must be different
• Start and end symbol must be same
• Every 'a' should be followed by 'b'
• Every 'a' should never followed by 'b'
• Every 'a' should followed by 'bb'
• Every 'a' should never followed by 'bb'
• DFA for aⁿb^m | n,m ≥ 1
• DFA for aⁿb^m | n,m ≥ 0
• DFA for aⁿb^mc^l | n,m,l ≥ 1
• DFA for aⁿb^mc^l | n,m,l ≥ 0
• DFA such that second sybmol from L.H.S. should be 'a'

DFA Operations

• DFA Union
• DFA Concatination
• DFA Cross Product
• DFA Complementation
• DFA Reversal

Minimization of DFA

• DFA Minimization
• Example 1
• Example 2

NFA

• NFA Introduction
• NFA for strings containing a
• NFA for strings ends with a
• Set Substitution Method

FA with Output

• FA with output
• Moore Machine
• Mealy Machine
• Moore Example
• Mealy Machine for 1's complement
• Mealy Machine for 2's complement

Regularity Check of grammar/language

• Regularity Check of Language
• Example 1
• Example 2
• Example 3
• Closure Properties

Finite automata to Regular Grammar

• FA to Right Linear Grammar
• FA to Left Linear Grammar
• Right Linear Grammar to FA
• Left Linear Grammar to FA

Context Free Grammar

• CFG Introduction
• CFG Membership Algo Introduction
• Elimination of &epsilpn; production
• Elimination of Unit production
• Elimination of Useless symbol
• CNF Form
• Closure Properties

PDA

• PDA Introduction
• DPDA for aⁿbⁿ n≥1
• DPDA for number of a(w) = number of b(w)
• DPDA for aⁿbⁿc^m n,m≥1
• DPDA for aⁿb^mc^c n,m≥1
• DPDA for aⁿbⁿc^md^m n,m≥1
• DPDA for aⁿb²ⁿ n≥1
• DPDA for aⁿb²ⁿ⁺¹ n≥1
• DPDA for wcw^R w ε (a,b)^*
• NPDA for ww^R w ε (a,b)^*

Turing Machine

• Turing Machine Introduction
• TM for aⁿbⁿcⁿ | n ≥ 1
• TM for 1's complement
• TM for 2's complement
• TM as Adder
• TM as Comparator
• TM as Copier
• Turing Thesis
• Linear Bounded Automata
• Recursive Enumerable Language
• Recursive Language