DFA (Deterministic Finite Automaton)Automaton Repres‐ entation  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 (Nondeterministic Finite Automaton)Formal Definition  M=(Q,Σ,Δ,S,F)  Q: Set of states  {q0,q1,q2}  Σ: input alphabet  {a,b}  Δ: transition function  Δ(q,x)={q1,q2,...} (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 Conversion1. 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 
  NFA to DFA Conversion (cont)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 RegexL1 ∪ L2  Initial state has two ε transi‐ tions, one to L1 and one to L2  L1L2L1L2  L1 accept state tranitions (ε) to L2 initial state  L1*  New initial state transitions to L1 initial state. New accept state transitions (ε) from L1 accept state. Initial to accept state transition transitions (ε) and vice versa.  L1R (reverse)  Reverse all transitions. Make initial state accepting state and vice versa.  !(L1) Complement  Accepting states become nonaccepting 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 ε.
Intersection DFA1 ∩ DFA2Transitions M1 : q1→ →q2 M2 : p1→ →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 ExpressionsL(r1+r2)  = L(r1) ∪ L(r2)  L(r1•r2)  = L(r1)L(r2)  L(r1*)  = (L(r1))*  L(a)  = {a} 
NFA to Regular Language1. 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 expression: r = r1 r2(r4+r3r1r2)* where: r1: initial → initial r2: initial → accepting r3: accepting → initial r4: accepting → accepting 
Proving Regularity with Pumping LemmaProve 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 contradiction:  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'=xy z∉L for some i≠1 

Created By
Metadata
Comments
No comments yet. Add yours below!
Add a Comment
Related Cheat Sheets