<- previous index next ->
The Pumping Lemma is generally used to prove a language is not context free.
If a PDA machine can be constructed to exactly accept
a language, then the language is a Context Free Language.
If a Context Free Grammar can be constructed to exactly generate the
strings in a language, then the language is Context Free.
To prove a language is not context free requires a specific definition of
the language and the use of the Pumping Lemma for Context Free Languages.
A note about proofs using the Pumping Lemma:
Given: Formal statements A and B.
A implies B.
If you can prove B is false, then you have proved A is false.
A B | A implies B
-----+------------
F F | T
F T | T (you can prove anything to be true with a false premise)
T F | F
T T | T
For the Pumping Lemma, the statement "A" is "L is a Context Free Language",
The statement "B" is a statement from the Predicate Calculus.
(This is a plain text file that uses words for the upside down A that
reads 'for all' and the backwards E that reads 'there exists')
Formal statement of the Pumping Lemma:
L is a Context Free Language implies
(there exists n)(for all z)[z in L and |z|>=n implies
{(there exists u,v,w,x,y)(z = uvwxy and |vwx|<=n and |vx|>=1 and
i i
(for all i>=0)(uv wx y is in L) )}]
The two commonest ways to use the Pumping Lemma to prove a language
is NOT context free are:
a) show that there is no possible n for the (there exists n),
this is usually accomplished by showing a contradiction such
as (n+1)(n+1) < n*n+n
b) show there is no way to partition some z into u,v,w,x,y such that
i i
uv wx y is in L, typically for a value i=0 or i=2.
Be sure to cover all cases by argument or enumerating cases.
[This gives a contradiction to the (for all z) clause.]
Some Context free languages and corresponding grammars:
i i
L={a b | i>=1} S->ab | aSb
2i 3i
L={a b | i>=1} S-> aabbb | aaSbbb [any pair of constants for 2,3]
i j i
L={a b c | i,j>=1} S->aBc | aSc B->b | bB
i i j
L={a b c | i,j>=1} S->DC D->ab | aDb C->c | cC
i i j j
L={a b a b | i,j>=1} S->CC C->ab | aCb
i i
L={ua wb y | i>=1 and u,w,y any fixed strings} S->uDy D->awb | aDb
R R
L={ww | w in Sigma star and w is w written backwards} S->xx | xSx
for all x in Sigma
Some languages that are NOT Context Free Languages
L={ww | w in Sigma star}
i i i
L={a b c | i>=1}
i j k
L={a b c | k > j > i >=1}
f(i) i
L={a b | i>=1} where f(i)=i**2 f(i) is the ith prime,
f(i) not bounded by a constant times i
meaning f(i) is not linear
i j i j
L={a b c d | i, j>=1}
You may be proving a lemma, a theorem, a corollary, etc
A proof is based on:
definition(s)
axioms
postulates
rules of inference (typical normal logic and mathematics)
To be accepted as "true" or "valid"
Recognized people in the field need to agree your
definitions are reasonable
axioms, postulates, ... are reasonable
rules of inference are reasonable and correctly applied
"True" and "Valid" are human intuitive judgments but can be
based on solid reasoning as presented in a proof.
Types of proofs include:
Direct proof (typical in Euclidean plane geometry proofs)
Write down line by line provable statements,
(e.g. definition, axiom, statement that follows from applying
the axiom to the definition, statement that follows from
applying a rule of inference from prior lines, etc.)
Proof by contradiction:
Given definitions, axioms, rules of inference
Assume Statement_A
use proof technique to derive a contradiction
(e.g. prove not Statement_A or prove Statement_B = not Statement_B,
like 1 = 2 or n > 2n)
Proof by induction (on Natural numbers)
Given a statement based on, say n, where n ranges over natural numbers
Prove the statement for n=0 or n=1
a) Prove the statement for n+1 assuming the statement true for n
b) Prove the statement for n+1 assuming the statement true for n in 1..n
Prove two sets A and B are equal, prove part 1, A is a subset of B
prove part 2, B is a subset of A
Prove two machines M1 and M2 are equal,
prove part 1 that machine M1 can simulate machine M2
prove part 2 that machine M2 can simulate machine M1
Limits on proofs:
Godel incompleteness theorem:
a) Any formal system with enough power to handle arithmetic will
have true theorems that are unprovable in the formal system.
(He proved it with Turing machines.)
b) Adding axioms to the system in order to be able to prove all the
"true" (valid) theorems will make the system "inconsistent."
Inconsistent means a theorem can be proved that is not accepted
as "true" (valid).
c) Technically, any formal system with enough power to do arithmetic
is either incomplete or inconsistent.
Given two CFG's G1 = (V1, T1, P1, S1) for language L1(G1)
G2 = (V2, T2, P2, S2) for language L2(G2)
Rename variables until V1 intersect V2 is Phi.
We can easily get CFG's for the following languages:
L1 union L2 = L3(G3)
G3 = (V1 union V2 union {S3}, T1 union T2, P1+P2+P3, S3)
S3 -> S1 | S2
L1 concatenated L2 = L4(G4)
G4 = (V1 union V2 union {S4}, T1 union T2, P1+P2+P4, S4)
S4 -> S1S2
L1 star = L5(G5)
G5 = (V1 union V2 union {S5}, T1 union T2, P1+P2+P5, S5)
S5 -> S5S1 | epsilon
L2 substituted for terminal "a" in L1 = L6(G6)
G6 = (V1 union V2, T1-{a} union T2, P6+P2, S1)
P6 is P1 with every occurrence of "a" replaced with S2.
Notice that L1 intersect L2 may not be a CFG.
i i j i j i
Example: L1={a b c | i,j>0} L2={a b c | i,j>0} are CFG's
i i i
but L1 intersect L2 = {a b c | i>0} which is not a CFG.
The complement of L1 may not be a CFG.
The difference of two CFG's may not be a CFG.
The intersection of a Context Free Language with a Regular Language
is a Context Free Language.
As a supplement, the following shows how to take a CFG and possibly
use 'yacc' or 'bison' to build a parser for the grammar.
The steps are to create a file xxx.y that includes the grammar,
and a file that is a main program that runs the parser.
An example grammar is coded in acfg.y
and a sample main program is coded in yymain.c
One possible set of commands to run the sample is:
bison acfg.y
gcc yymain.c acfg.tab.c
a.out
abaa
The output from this run shows the input being read and the rules
being applied:
read a
read b
read a
A -> ba
read a
read end of line \n converted to 0
S -> a
S -> aAS
accepted
A grammar that may be of more interest is a grammar for a calculator.
Simple statement such as
a=2
b=3
a+b
that prints the answer 5 can be coded as a CFG.
The following example uses bison format and has a simple lexical
analysis built in for single letter variables.
calc.y and a sample main program yymain.c
One possible set of commands to run calc is:
bison calc.y
gcc -o calc yymain.c calc.tab.c
calc
a=2
b=3
a+b
You should get the result 5 printed. See the grammar to find out what
other operations are available
<- previous index next ->