DFA (Deterministic Finite Automaton)Automaton Representation | 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-deterministic 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 | 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 ε transitions, one to L1 and one to L2 | L1L2 | 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 non-accepting 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→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 ExpressionsL(r1+r2) | = L(r1) ∪ L(r2) | L(r1•r2) | = L(r1)L(r2) | L(r1*) | = (L(r1))* | L(a) | = {a} |
Precedence: * → + → • → +
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+r3r1*r2)* 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'=xyiz∉L for some i≠1 |
|
Created By
Metadata
Favourited By
Comments
No comments yet. Add yours below!
Add a Comment
Related Cheat Sheets
More Cheat Sheets by Vipera