Cheatography

# Automata Cheat Sheet by Vipera

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­tionsM1: q1→a→q2 M2: p1→a→p2 DFA M: (q1,p1)→a→(q2,p2) Initial StateM1: q0 M2: p0 DFA M: (q0,p0) Accept StateM1: 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