DefinitIons
|
Finite Automaton(FA) 5-tuple(Q,Σ,δ,q,F) where
i)Q = states
ii)Σ = input alphabet
iii)δ:QxΣ -> Q = transitions
iv)qϵQ = start state
v)F = accept states
|
|
Regular Language(RL) Is recognized by some FA and is closed under the operations:
i)∪
ii)∘
iii)*
iv)∩
v)Complementation
|
|
Deterministic Finite Automaton(DFA) FA where there is only one state that can be transitioned to from the current state and current input symbol.
|
|
Nondeterministic Finite Automaton(NFA) FA where there is one or more states that can be transitioned to from the current state and current input symbol.
|
|
Power Set The set of all subsets of a language.
Has size 2|A|.
|
|
Regular Expression(RE) Is one of the following:
i)a such that aϵΣ
ii)ε
iii)∅
iv)S∪T where S,T are RE
v)S∘T where S,T are RE
vi)S* where S is a RE
|
|
Generalized NFA(GNFA) 5-tuple(Q,Σ,δ,q,a) where
i)Q =states
ii)Σ = input alphabet
iii)δ:(Q-{a})x(Q-{q}) -> R = transitions
iv)qϵQ = start state
v)aϵQ = accept state
Also must meet the following conditions:
i)Start state has transitions arrows going out, but none coming into itself
ii)There is only one accept state with transition arrows coming in, but none going out from itself
iii)Except for the start and accept states, only one arrow goes from every state to every other state, including an arrow to itself
|
|
|
CFL Definitions
|
Context Free Languages(CFL) Languages described by context free grammars and pushdown automata. They include all RL.
Any language that can be generated by a CFG.
|
|
Context Free Grammar(CFG) 4-tuple(V,Σ,R,S), where:
i)V = set of variables
ii)Σ = set of terminals, disjoint from V
iii)R = set of rules, with each rule being a variable and a string of variables and terminals
iv)SϵV = start variable
|
|
Ambiguity A string is ambiguous if there is more than one way to generate the string. If a CFG has an ambiguous string, then the grammar is ambiguous.
If an ambiguous CFG generates a CFL that can only be generated by ambiguous grammars, then it is inherently ambiguous.
|
|
Leftmost Derivation At each step of string derivation, the leftmost variable is replaced.
|
|
Chomsky Normal Form(CNF) Every rule is of the form A->BC or A->a, where a is a terminal and A,B,C are variables. We allow S->e, where S is the start variable.
|
|
Pushdown Automaton(PDA) 6-tuple(Q,Σ,Γ,δ,q,F), where
i)Q = states
ii),Σ, = input alphabet
iii)Γ = stack alphabet
iv)δ:QxΣxΓ -> P(QxΓ) = transition function
v)qϵQ = start state
vi)FϵQ = accept states
By definition, they are nondeterministic.
|
|
|
Theorems, Lemmas, Corallaries for RL
Every NFA has an equivalent DFA |
A language is regular iff some NFA recognizes it |
If a language is described by a RE, then it is regular |
If a language is regular, it is described by a RE |
A language is regular iff some RE describes it |
Pigeonhole Principle: If we stuff n items into less than n holes, at least one hole must have more than one item in it |
There is an algorithm that can determine if two FA are equivalent |
Pumping Lemma for RL
|
Let A be a RL. Then there exists a number p(pumping length of A), such that any string from the language A having length at least p can be broken into three pieces, s=xyz such that: i)∀ i≥0, xyiz is an element of A
ii)|y|>0
iii)|xy|≤p
|
Theorem, Lemmas, Corallaries for CFL
Any CFL can be generated by a CFG in Chomsky Normal Form. |
A language is context free(CFL) iff some PDA recognizes it. |
If a language is context free(CFL), then some PDA recognizes it. |
If a PDA recognizes some language, then the language is contex free(CFL). |
Every regular language is context free. |
Pumping Lemma for CFL
|
If A is a CFL, then there is a number p(pumping length of A) where, if s is any string in A with length at least p, then s may be divided into 5 pieces, s = uvxyz where: i)∀ i≥0, uvixyiz is an element of A
ii)|vy|>0
iii)|vxy|≤p
|
|
Contradictions by condition: ii)At least one of v and y cannot be the empty string
iii)Can be used in showing some languages are not CFL
|
|
Created By
Metadata
Favourited By
Comments
No comments yet. Add yours below!
Add a Comment