Show Menu
Cheatography

DFA, NFA, Regex and Pumping Lemma

DFA (Deter­min­istic Finite Automaton)

Automaton Repres­ent­ation
M=(Q,Σ­,δ,­q0,F)
Q: Set of states
{q0,q1,q2}
Σ: input alphabet
{a,b} & ε ∉ Σ
δ: transition function
δ(q,x)=q'
q0: initial state
F: set of accepting states
{q2}
Language of Automaton
L(M)={ w∈Σ* : δ*(q0,­w)∈F}
Languages are regular if a DFA exists for that language.
DFA: Each state has one transition for evrey alphabet

NFA (Non-d­ete­rmi­nistic Finite Automaton)

Formal Definition
M=(Q­,­Σ,­­Δ,S,F)
Q: Set of states
{q0,q1,q2}
Σ: input alphabet
{a,b}
Δ: transition function
Δ(q,x)­={q­1,q­2,...} (include ε)
S: initial states
{q0}
F: set of accepting states
{q2}
Language of Automaton
L(M) = {w1,w2­,...,wn}
NFA: Each state can have different transition with the same language output
 

NFA to DFA Conversion

1. Set initial state of NFA to initial state of DFA
2. Take the states in the DFA, and compute in the NFA what the union Δ of those states for each letter in the alphabet and add them as new states in the DFA.
For example if (q0,a) takes you to {q1,q2} add a state {q1,q2}. If there isn't one, the add state null
3. Set every DFA state as accepting if it contains an accepting state from the NFA
The language for the NFA (M) and DFA (M') are equivalent
L(M)=L(M')

Properties of Regex

L1 ∪ L2
Initial state has two ε transi­tions, one to L1 and one to L2
L1L2
L1 accept state tranitions (ε) to L2 initial state
L1*
New initial state transi­tions to L1 initial state. New accept state transi­tions (ε) from L1 accept state. Initial to accept state transition transi­tions (ε) and vice versa.
L1R (reverse)
Reverse all transi­tions. Make initial state accepting state and vice versa.
!(L1) Complement
Accepting states become non-ac­cepting and vice versa
L1 ∩ L2
!( !(L1) ∪ !(L2) )
P.S. To turn multiple states to one accept state in an NFA, just add a new accept state, and add transition to the old accept states with language ε.
 

Inters­ection DFA1 ∩ DFA2

Transi­tions
M1: q1→a→q2
M2: p1→a→p2
DFA M: (q1,p1)→a→(q2,p2)
Initial State
M1: q0
M2: p0
DFA M: (q0,p0)
Accept State
M1: qi
M2: pj,pk
DFA M: (qi,pj) , (qi,pk)

Regular Expres­sions

L(r1+r2)
= L(r1) ∪ L(r2)
L(r1•r2)
= L(r1)L(r2)
L(r1*)
= (L(r1))*
L(a)
= {a}
Preced­ence: * → + → • → +

NFA to Regular Language

1. Transform each transition into regex (e.g. (a,b) is a+b
2. Remove each state one by one, until you are left with the initial and accepting state
3. Resulting regular expres­sion: r = r1* r2(r4+­r3r­1*r2)* where:
r1: initial → initial
r2: initial → accepting
r3: accepting → initial
r4: accepting → accepting

Proving Regularity with Pumping Lemma

Prove than an infinite language L is not regular:
1. Assume L is regular
2. The pumping lemma should hold for L
3. Use the pumping lemma to obtain a contra­dic­tion:
 ­ a. Let m be the critical length for L
 ­ b. Choose a particular string w∈L which satisfies the length condition |w|≥m
 ­ c. Write w=xyz
 ­ d. Show that w'=xyiz∉L for some i≠1
           
 

Metadata

  • Languages:
  • Published: 11th December, 2020
  • Last Updated: 12th December, 2020

Favourited By

tenlaven

Comments

No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.

          Related Cheat Sheets

          Regular Expressions Cheat Sheet
          Perl Reference Card Cheat Sheet

          More Cheat Sheets by Vipera

          Automata - CFG & PDA Cheat Sheet