Context-Free Languages
Context-Free Grammar
Subjects to be Learned
- Context-Free Grammar
- Context-Free Languages
- Push Down Automata
Contents
Earlier in the discussion of grammars we saw context-free grammars.
They are grammars whose productions have the form
X -> , where X is a nonterminal and
is a nonempty string of terminals
and nonterminals.
The set of strings generated by a context-free grammar is called a context-free
language and context-free languages can describe many practically important
systems. Most programming languages can be approximated by context-free grammar
and compilers for them have been developed based on properties of context-free
languages. Let us define context-free
grammars and context-free languages here.
Definition (Context-Free Grammar) :
A 4-tuple G = < V , , S , P >
is a context-free grammar (CFG) if
V and are finite sets sharing no elements
between them, S V is the start
symbol, and P is a finite set of productions of the form X ->
, where
X V , and
( V )^{*} .
A language is a context-free language (CFL)
if all of its strings are generated by a context-free grammar.
Example 1:
L_{1} = { a^{n}b^{n} | n is a positive integer }
is a context-free language. For the following context-free grammar
G_{1} = < V_{1} , , S ,
P_{1} > generates L_{1} :
V_{1} = { S } , = { a , b } and
P_{1} = { S -> aSb , S -> ab }.
Example 2:
L_{2} = { ww^{r}| w
{a, b }^{+} } is a context-free language ,
where w is a non-empty string and w^{r} denotes the reversal of string w,
that is, w is spelled backward to obtain w^{r} . For the following
context-free grammar
G_{2} = < V_{2} , , S ,
P_{2} >
generates L_{2} :
V_{2} = { S } , = { a , b } and
P_{2} = { S -> aSa , S -> bSb , S -> aa , S -> bb }.
Example 3:
Let L_{3} be the set of algebraic expressions involving identifiers x and y,
operations + and * and left and right parentheses. Then L_{3} is a context-free
language.
For the following context-free grammar
G_{3} = < V_{3} , _{3}, S ,
P_{3} > generates L_{3} :
V_{3} = { S } , _{3}
= { x , y , ( , ) , + , * } and
P_{3} = { S -> ( S + S ) , S -> S*S , S -> x , S -> y }.
Example 4:
Portions of the syntaxes of programming languages can be described by context-free
grammars. For example
{ < statement > -> < if-statement > , < statement > -> <
for-statement > ,
< statement > -> < assignment > , . . . ,
< if-statement > -> if ( < expression > ) < statement > ,
< for-statement > -> for ( < expression > ; < expression >
; < expression > )
< statement > , . . . , < expression > -> < algebraic-expression > ,
< expression >
-> < logical-expression > , . . . } .
Properties of Context-Free Language
Theorem 1:
Let L_{1} and L_{2} be context-free languages.
Then L_{1} L_{2} , L_{1}L_{2} ,
and L_{1}^{*} are context-free languages.
Outline of Proof
This theorem can be verified by constructing context-free grammars
for union, concatenation and Kleene star of context-free grammars as follows:
Let G_{1} = < V_{1} , ,
S_{1} , P_{1} > and G_{2} = < V_{2} ,
,
S_{2} , P_{2} > be context-free grammars generating L_{1} and
L_{2} , respectively.
Then for L_{1} L_{2} , first relabel symbols
of V_{2} , if necessary, so that V_{1} and V_{2} don't share any
symbols. Then let S_{u} be a symbol
which is not in V_{1} V_{2} .
Next define V_{u} = V_{1} V_{2}
{ S_{u} } and
P_{u} = P_{1} P_{2}
{ S_{u} -> S_{1} ,
S_{u} -> S_{2} } .
Then it can be easily seen that G_{u} = < V_{u} ,
,
S_{u} , P_{u} > is a context-free grammar that generates the language
L_{1} L_{2} .
Similarly for L_{1}L_{2} , first relabel symbols of V_{2} ,
if necessary, so that V_{1} and V_{2} don't share any symbols.
Then let S_{c} be a symbol
which is not in V_{1} V_{2} .
Next define V_{c} = V_{1} V_{2}
{ S_{c} } and
P_{c} = P_{1} P_{2}
{ S_{c} -> S_{1}S_{2} } .
Then it can be easily seen that G_{c} = < V_{c} ,
,
S_{c} , P_{c} > is a context-free grammar that generates the language
L_{1}L_{2} .
For L_{1}^{*} , let S_{s} be a symbol
which is not in V_{1} . Then let P_{s} = P_{1}
{ S_{s} -> S_{s}S_{1} ,
S_{s} -> } .
It can be seen that the grammar G_{s} = < V_{s} ,
,
S_{s} , P_{s} > is a context-free grammar that generates the language
L_{1}^{*} .
Pushdown Automata
Like regular languages which are accepted by finite automata, context-free
languages are also accepted by automata but not finite automata. They need a little more
complex automata called pushdown automata.
Let us consider a context-free language a^{n}b^{n} .
Any string of this language can be tested for the membership for the language
by a finite automaton if there is a memory such as a pushdown stack that can store
a's of a given input string. For example, as a's are read by the finite
automaton,
push them into the stack.
As soon as the symbol b appears stop storing a's and start popping a's one
by one every time a b is read.
If another a (or anything other than b) is read after the first b, reject the string.
When all the symbols of the input string are read, check the stack.
If it is empty, accept the string. Otherwise reject it.
This automaton behaves like a finite automaton except the following two points: First,
its next state is determined not only by the input symbol being read, but also
by the symbol at the top of the stack. Second, the contents of the stack can also
be changed
every time an input symbol is read. Thus its transition function specifies the new top of
the stack contents as well as the next state.
Let us define this new type of automaton formally.
A pushdown automaton ( or PDA for short )
is a 7-tuple M = < Q , ,
, q_{0} , Z_{0} , A ,
> , where
Q is a finite set of states,
and
are finite sets ( the input and stack alphabet, respectively ).
q_{0} is the initial state,
Z_{0} is the initial stack symbol and it is a member of ,
A is the set of accepting states
is the transition function and
: Q
(
( }
-> 2^{ Q}
^{*}.
Thus ( p , a , X ) =
( q , ) means the following:
The automaton moves from the current
state of p to the next state q when it sees an input symbol a at the input and X at the top
of the stack, and it replaces X with the string
at the top of the stack.
Example 1 :
Let us consider the pushdown automaton < Q , ,
, q_{0} , Z_{0} , A ,
> , where
Q = { q_{0} , q_{1} , q_{2} } ,
= { a , b } ,
= { a , b , Z_{0} } ,
A = { q_{2} } and let be as given in the following
table:
State | Input | Top of Stack | Move |
q_{0} | a | Z_{0} | ( q_{0} , aZ _{0} ) |
q_{0} | a | a | ( q_{0} , aa ) |
q_{0} | b | a | ( q_{1} , ) |
q_{1} | b | a | ( q_{1} , ) |
q_{1} | | Z_{0} | ( q_{2} , Z_{0} ) |
This pushdown automaton accepts the language a^{n}b^{n} .
To describe the operation of a PDA we are going to use a configuration of PDA.
A configuration of a PDA M = < Q ,
,
, q_{0} , Z_{0} , A ,
> is a triple
( q , x , ) , where q is the state the PDA is currently in,
x is the unread portion of the input string and
is the current stack contents, where the input is read from left to right
and the top of the stack corresponds to the leftmost symbol of
. To express that the PDA moves from
configuration ( p , x , ) to configuration
( q , y , ) in a single move
(a single application of the transition function)
we write
( p , x , )
( q , y , ) .
If ( q , y , ) is reached from
( p , x , ) by a sequence of zero or more moves,
we write
( p , x , )
^{*}
( q , y , ) .
Let us now see how the PDA of Example 1 operates when it is given the string aabb ,
for example.
Initially its configuration is ( q_{0} , aabb , Z_{0} ).
After reading the first a, its configuration is ( q_{0} , abb , aZ_{0} ).
After reading the second a, it is ( q_{0} , bb , aaZ_{0} ).
Then when the first b is read, it moves to state
q_{1} and pops a from the top of the stack. Thus the configuration is
( q_{1} , b , aZ_{0} ). When the second b is read, another a is
popped from the top of the stack and the PDA stays in state q_{1} .
Thus the configuration is ( q_{1} , ,
Z_{0} ). Next it moves to the state q_{2} which is the accepting state.
Thus aabb is accepted by this PDA. This entire process can be expressed using
the configurations as
( q_{0} , aabb , Z_{0} )
( q_{0} , abb , aZ_{0} )
( q_{0} , bb , aaZ_{0} )
( q_{1} , b , aZ_{0} )
( q_{1} , , Z_{0} )
( q_{2} , , Z_{0} ).
If we are not interested in the intermediate steps, we can also write
( q_{0} , aabb , Z_{0} ) ^{*}
( q_{2} , , Z_{0} ) .
A string x is accepted by a PDA
(a.k.a. acceptance by final state) if
(q_{0}, x, Z_{0}) ^{*}
(q, , ), for some
in ^{*}, and
an accepting state q.
Like FAs, PDAs can also be represented by transition diagrams. For PDAs, however,
arcs are labeled differently than FAs. If ( q , a , X ) =
( p , ) , then an arc from state p to state q is added to
the diagram and it is labeled with ( a , X / )
indicating that X at the top of the stack is replaced by
upon reading a from the input.
For example the transition diagram of the PDA of Example 1 is as shown below.
Example 2 :
Let us consider the pushdown automaton < Q , ,
, q_{0} , Z_{0} , A ,
> , where
Q = { q_{0} , q_{1} , q_{2} } ,
= { a , b , c } , =
{ a , b , Z_{0} } , A = { q_{2} } and let
be as given in the following table:
State | Input | Top of Stack | Move |
q_{0} | a | Z_{0} | ( q_{0} , aZ _{0} ) |
q_{0} | b | Z_{0} | ( q_{0} , bZ _{0} ) |
q_{0} | a | | ( q_{0} , a ) |
q_{0} | b | | ( q_{0} , b ) |
q_{0} | c | | ( q_{1} , ) |
q_{1} | a | a | ( q_{1} , ) |
q_{1} | b | b | ( q_{1} , ) |
q_{1} | | Z_{0} | ( q_{2} , Z_{0} ) |
In this table represents either a or b.
This pushdown automaton accepts the language { wcw^{r} | w
{ a , b }^{*} } , which is
the set of palindromes with c in the middle.
For example for the input abbcbba, it goes through the following configurations and
accepts it.
( q_{0} , abbcbba , Z_{0} )
( q_{0} , bbcbba , aZ_{0} )
( q_{0} , bcbba , baZ_{0} )
( q_{0} , cbba , bbaZ_{0} )
( q_{1} , bba , bbaZ_{0} )
( q_{1} , ba , baZ_{0} )
( q_{1} , a , aZ_{0} )
( q_{1} , , Z_{0} )
( q_{2} , , Z_{0} ) .
This PDA pushes all the a's and b's in the input into stack until c is encountered.
When c is detected, it ignores c and from that point on
if the top of the stack matches the input symbol, it pops the stack.
When there are no more unread input symbols and Z_{0} is at the top of the stack,
it accepts the input string. Otherwise it rejects the input string.
The transition diagram of the PDA of Example 2 is as shown below.
In the figure ,
_{1} and
_{2} represent a or b.
Further topics on CFL
- PDA and Context-Free Language
There is a procedure to construct a PDA that accepts the language generated by
a given context-free grammar and conversely.
That means that a language is context-free if and only if there is a PDA
that accepts it. Those procedures are omitted here.
- Pumping Lemma for Context-Free Language
Let L be a CFL. Then there is a positive integer n such that for any string u in L
with |u| n , there are strings
v, w, x, y and z which satisfy
u = vwxyz
|wy| > 0
|wxy| n
for every integer m 0 ,
vw^{m}xy^{m}z L
- Parsing and Parsers for CFL
Consider the algebraic expression x + yz. Though we are accustomed to interpreting
this as x + (yz) i.e. compute yz first, then add the result to x, it could also be
interpreted as ( x + y )z meaning that first compute x + y, then multiply the result
by z. Thus if a computer is given the string x + yz, it does not know which
interpretation to use unless it is explicitly instructed to follow one or the other.
Similar things happen when English sentences are processed by computers (or people
as well for that matter). For example in the sentence "A man bites a dog", native
English speakers know that it is the dog that bites and not the other way round.
"A dog" is the subject, "bites" is the verb and "a man" is the object of the verb.
However, a computer like non-English speaking people must be told how to interpret
sentences such as the first noun phrase (" A dog") is usually the subject
of a sentence, a verb phrase usually follow the noun phrase and the first word
in the verb phrase is the verb and it is followed by noun phrases reprtesenting
object(s) of the verb.
Parsing is the process of interpreting given input strings according to predetermined
rules i.e. productions of grammars. By parsing sentences we identify the parts of the
sentences and
determine the strutures of the sentences so that their meanings can be understood
correctly.
Contect-free grammars are powerful grammars. They can describe much of programming
languages and basic structures of natural languages. Thus they are widely used
for compilers for high level programming languages and natural language processing systems.
The parsing for context-free languages and regular languages have been extensively
studied. However, we are not going to study parsing here. Interested readers are
referred to the textbook and other sources.
????
references on Parsing
????
Test Your Understanding of Contect-Free Language
Indicate which of the following statements are correct and which are not.
Click True or Fals , then Submit.
Next -- Turing Machines
Back to Schedule
Back to Table of Contents