CONTEXT-FREE LANGUAGES
Posted byI. CONTEXT - FREE GRAMMAR
* Definition of Context-Free Grammar
Just as any formal grammar, a context-free grammar G can be defined as a 4-tuple
G = (Vt,Vn,P,S) where:
- Vt is a finite set of terminals
- Vn is a finite set of non-terminals
- P is a finite set of production rules
- S is an element of Vn, the distinguished starting non-terminal and elements of P are of the form.
- Example 1:
The canonical example of a context free grammar is parentheses matching, which is representative of the general case. There are two terminal symbols ( and ) and one nonterminal symbol S.
- Example 2:
A second canonical example is two different kinds of matching nested parentheses, described by the productions:
S → SS
S → ()
S → (S)
S → []
S → [S]
with terminal symbols [ ] ( ) and nonterminal S.
- Example 3:
The terminals here are a and b, while the only non-terminal is S. The language described is all nonempty strings of as and bs that end in a.This grammar is regular: no rule has more than one nonterminal in its right-hand side, and each of these nonterminals is at the same end of the right-hand side.
S → a
S → aS
S → bS
- Example 4:
In a context-free grammar, we can pair up characters the way we do with brackets. The simplest example:
S → aSb
S → ab
This grammar generates the language , which is not regular The special character ε stands for the empty string. By changing the above grammar to
S → aSb ε
we obtain a grammar generating the language instead. This differs only in that it contains the empty string while the original grammar did not.
- Example 5:
Here is a context-free grammar for syntactically correct infix algebraic expressions in the variables x, y and z:
S → x
S → y
S → z
S → S + S
S → S - S
S → S * S
S → S / S
S → ( S )
S → y
S → z
S → S + S
S → S - S
S → S * S
S → S / S
S → ( S )
A context-free grammar for the language consisting of all strings over {a,b} containing an unequal number of a's and b's:
S → U V
U → TaU TaT
V → TbV TbT
T → aTbT bTaT ε
U → TaU TaT
V → TbV TbT
T → aTbT bTaT ε
- Example 7:
Another example of a non-regular language is . It is context-free as it can be generated by the following context-free grammar:
S → bSbb A
A → aA ε
A → aA ε
* Designing Context-Free Grammar
• Some basic techniques:
1. Matching – enforcing the fact that your grammar generates matching pairs of symbols.
2. Using recursive relationships – when you can represent strings in the language interms of shorter strings in the language.
3. Thinking of each nonterminal A as representing a language of all strings w deriv-able from A. Then, combining these languages into one, using the rules.
* Ambiguity
A grammar that generates a sentence for which there are two or more distinct parse trees are
said to be ambiguous. The ambiguity occurs because the grammar specifies slightly less syntactic
structure.
* Chomsky Normal Form
In computer science, a context-free grammar is said to be in Chomsky normal form if all of its
production rules are of the form:
ABC or
Aα or
Sε
where A, B and C are nonterminal symbols, α is a terminal form (a symbol that represents a constant value), S is the start symbol, and ε is the empty string. Also, neither B nor C may be the start symbol.
II. PUSHDOWN AUTOMATA
* Formal Definition of Pushdown Automata
A NPDA W can be defined as a 7-tuple W = (Q,Σ,Φ,σ,s,Ω,F) where
• Q is a finite set of states
• Σ is a finite set of the input alphabet
• Φ is a finite set of the stack alphabet
• σ (or sometimes δ) is a finite transition relation (Q x (Σ U {ε} x Ø) ----> P (Q x Ø)
• s is an element of Q the start state
• Ω is the initial stack symbol
• F is subset of Q, consisting of the final states.
* Examples of Pushdown Automata
The following is the formal description of the PDA which recognizes the language by final state:
PDA for (by final state) M = (Q, Σ , Γ , δ , p , Z, F), where
Q = {p,q,r}
Σ = {0,1}
Γ = {A,Z}
F = {r}
δ consists of the following six instructions:
(p,0,Z,p,AZ), (p,0,A,p,AA), (p,ε,Z,q,Z), (p,ε,A,q,A), (q,1,A,q,ε), and (q,ε,Z,r,Z).
In words, in state p for each symbol 0 read, one A is pushed onto the stack. Pushing symbol A on
top of another A is formalized as replacing top A by AA. In state q for each symbol 1 read one A
is popped. At any moment the automaton may move from state p to state q, while it may move
from state q to accepting state r only when the stack consists of a single Z.
There seems to be no generally used representation for PDA. Here we have depicted the
instruction (p,a,A,q,α) by an edge from state p to state q labelled by a;A / α (read a; replace A
by α)
* Equivalence of Context-Free Grammars with Pushdown Automata
- CFG and PDA are equivalent in power: a CFG generates a context-free language and
a PDA recognizes a context-free language.
- We show here how to convert a CFG into PDA that recognizes the language specified
by the CFG and vice versa - Application: this equivalence allows a CFG to be used to specify a programming language and the equivalent PDA to be used to implement its compiler.
Theorem 2.0 A language is context-free iff some pushdown automaton recognizes it.
Note: This means that:
1. if a language L is context-free then there is a PDA ML that recognizes it.
2. if a language L is recognized by a PDA GL that generates L.
Lemma 2.21 If a language is context-free then some pushdown automaton recognizes it.
Proof idea:
1. Let A be a CFL. From the definition we know that A has a CFG G,
that generates it.
2. We will show how to convert G into a PDA P that accepts strings if w generates if G generates w.
3. P will work by determining a derivation of w.
0 comments:
Post a Comment