Natural and Context-free Languages (CFLs)/Ambiguity contest
Rony
Chapter13Context-freeandnotContext-FreeLanguagesFile.pptContext-Free and
Noncontext-Free Languages
Chapter 13
Languages That Are and
Are Not Context-Free
a*b* is regular.
AnBn = {anbn : n 0} is context-free but not regular.
AnBnCn = {anbncn : n 0} is not context-free.
Languages and Machines
The Regular and the CF Languages
Theorem: The regular languages are a proper subset of the context-free languages.
Proof: In two parts:
- Every regular language is CF.
- There exists at least one language that is CF but not regular.
The Regular and the CF Languages
Lemma: Every regular language is CF.
Proof: Every FSM is (trivially) a PDA:
Given an FSM M = (K, , , s, A) and elements of of the form: ( p, c, q )
old state, input, new state
Construct a PDA M' = (K, , {}, , s, A). Each (p, c, q) becomes:
(( p, c, ), (q, ))
old state, input, don't new state don't
look at push on
stack stack
In other words, we just don’t use the stack.
There Exists at Least One Language that is CF but Not Regular
Lemma: There exists at least one language that is CF but not regular
Proof: {anbn, n 0} is context-free but not regular.
So the regular languages are a proper subset of the context-free languages.
How Many Context-Free Languages Are There?
Theorem: There is a countably infinite number of CFLs.
Proof:
● Upper bound: we can lexicographically enumerate
all the CFGs.
● Lower bound: {a}, {aa}, {aaa}, … are all CFLs.
How Many Context-Free Languages Are There?
There is an uncountable number of languages.
Thus there are more languages than there are context-free languages.
So there must exist some languages that are not context-free.
Example: {anbncn : n 0}
Showing that L is Context-Free
Techniques for showing that a language L is context-free:
1. Exhibit a context-free grammar for L.
2. Exhibit a PDA for L.
3. Use the closure properties of context-free languages.
Unfortunately, these are weaker than they are for
regular languages.
Showing that L is Not Context-Free
Remember the pumping argument for regular languages:
95.unknown
A Review of Parse Trees
A parse tree, derived by a grammar G = (V, , R, S), is a rooted, ordered tree in which:
● Every leaf node is labeled with an element of {},
● The root node is labeled S,
● Every other node is labeled with some element of V - ,
● If m is a nonleaf node labeled X and the children of m are labeled x1, x2, …, xn, then the rule X x1, x2, …, xn is in R.
Some Tree Basics
The height of a tree is the length of the longest path from the root to any leaf.
The branching factor of a tree is the largest number of daughter nodes associated with any node in the tree.
Theorem: The length of the yield of any tree T with height h and branching factor b is bh.
From Grammars to Trees
Given a context-free grammar G:
● Let n be the number of nonterminal symbols in G.
● Let b be the branching factor of G
Suppose that T is generated by G and no nonterminal appears more than once on any path:
The maximum height of T is:
The maximum length of T’s yield is:
64.unknown
The Context-Free Pumping Theorem
This time we use parse trees, not automata as the basis for our argument.
If w is “long”, then its parse trees must look like:
Choose one such tree such that there’s no other with fewer nodes.
The Context-Free Pumping Theorem
There is another derivation in G:
S * uXz * uxz,
in which, at the point labeled [1], the nonrecursive rule2 is used.
So uxz is also in L(G).
The Context-Free Pumping Theorem
There are infinitely many derivations in G, such as:
S * uXz * uvXyz * uvvXyyz * uvvxyyz
Those derivations produce the strings:
uv2xy2z, uv3xy3z, …
So all of those strings are also in L(G).
The Context-Free Pumping Theorem
If rule1 = X Xa, we could get v = .
If rule1 = X aX, we could get y = .
But it is not possible that both v and y are . If they were, then the derivation S * uXz * uxz would also yield w and it would create a parse tree with fewer nodes. But that contradicts the assumption that we started with a tree with the smallest possible number of nodes.
The Context-Free Pumping Theorem
The height of the subtree rooted at [1] is at most:
The Context-Free Pumping Theorem
The height of the subtree rooted at [1] is at most: n + 1
So |vxy| bn + 1.
The Context-Free Pumping Theorem
If L is a context-free language, then
k 1 ( strings w L, where |w| k
(u, v, x, y, z ( w = uvxyz,
vy ,
|vxy| k and
q 0 (uvqxyqz is in L)))).
k serves two roles:
● How long must w be to guarantee it is pumpable?
● What’s the bound on |vxy|?
Let n be the number of nonterminals in G.
Let b be the branching factor of G.
What Is k?
If height(T) > n, then some nonterminal occurs more than once on some path. So T is pumpable.
If height(T) n, then |uvxyz| bn.
So if |uvxyz| > bn, w = uvxyz must be pumpable.
How Long Must w be?
Assume that we are considering the bottom-most two instances of a repeated nonterminal. Then the yield of the upper one has length at most bn+1.
Assuming b 2, bn+1 > bn.
So let k = bn+1.
What’s the Bound on |vxy|?
The Context-Free Pumping Theorem
If L is a context-free language, then k 1, such that
strings w L, where |w| k,
u, v, x, y, z, such that: w = uvxyz,and
vy , and
|vxy| k, and
q 0, uvqxyqz is in L.
Proof: L is generated by some CFG G = (V, , R, S) with n nonterminal symbols and branching factor b. Let k be bn + 1. The longest string that can be generated by G with no repeated nonterminals in the resulting parse tree has length bn. Assuming that b 2, it must be the case that bn + 1 > bn. So let w be any string in L(G) where |w| k. Let T be any smallest parse tree for w. T must have height at least n + 1. Choose some path in T of length at least n + 1. Let X be the bottom-most repeated nonterminal along that path. Then w can be rewritten as uvxyz. The tree rooted at [1] has height at most n + 1. Thus its yield, vxy, has length less than or equal to bn + 1, which is k. vy since if vy were then there would be a smaller parse tree for w and we chose T so that that wasn’t so. uxz must be in L because rule2 could have been used immediately at [1]. For any q 1, uvqxyqz must be in L because rule1 could have been used q times before finally using rule2.
Regular vs CF Pumping Theorems
Similarities:
● We choose w, the string to be pumped.
● We choose a value for q that shows that w isn’t pumpable.
● We may apply closure theorems before we start.
Differences:
● Two regions, v and y, must be pumped in tandem.
● We don’t know anything about where in the strings v and y will
fall. All we know is that they are reasonably “close together”, i.e.,
|vxy| k.
● Either v or y could be empty, although not both.
An Example of Pumping: AnBnCn
AnBnCn = {anbncn, n 0}
An Example of Pumping: AnBnCn
AnBnCn = {anbncn, n 0}
Choose w = ak bk ck
1 | 2 | 3
An Example of Pumping: AnBnCn
AnBnCn = {anbncn, n 0}
Choose w = ak bk ck
1 | 2 | 3
If either v or y spans regions, then let q = 2 (i.e., pump in once). The resulting string will have letters out of order and thus not be in AnBnCn.
If both v and y each contain only one distinct character then set q to 2. Additional copies of at most two different characters are added, leaving the third unchanged. There are no longer equal numbers of the three letters, so the resulting string is not in AnBnCn.
An Example of Pumping: { , n 0}
L = { , n 0}
The elements of L:
| n | w |
| 0 | |
| 1 | a1 |
| 2 | a4 |
| 3 | a9 |
| 4 | a16 |
| 5 | a25 |
| 6 | a36 |
An Example of Pumping: { , n 0}
L = { , n 0}
If n = k2, then n2 = k4. Let w = .
An Example of Pumping: { : n 0}
L = { , n 0}. If n = k2, then n2 = k4. Let w = .
vy = ap, for some nonzero p.
Set q to 2. The resulting string, s, is . It must be in L. But it isn’t because it is too short:
w: next longer string in L:
(k2)2 a’s (k2 + 1)2 a’s
k4 a’s k4 + 2k2 + 1 a’s
For s to be in L, p = |vy| would have to be at least 2k2 + 1.
But |vxy| k, so p can’t be that large. Thus s is not in L and L is not context-free.
Another Example of Pumping
L = {anbman, n, m 0 and n m}.
Let w =
Another Example of Pumping
L = {anbman, n, m 0 and n m}.
Let w = akbkak
aaa … aaabbb … bbbaaa … aaa
| 1 | 2 | 3 |
Nested and Cross-Serial Dependencies
PalEven = {wwR : w {a, b}*}
a a b b a a
The dependencies are nested.
WcW = {wcw : w {a, b}*}
a a b c a a b
Cross-serial dependencies.
WcW = {wcw : w {a, b}*}
Let w = akbkcakbk.
aaa … aaabbb … bbbcaaa … aaabbb … bbb
| 1 | 2 |3| 4 | 5 |
Call the part before c the left side and the part after c the right side.
● If v or y overlaps region 3, set q to 0. The resulting string will no
longer contain a c.
● If both v and y occur before region 3 or they both occur after
region 3, then set q to 2. One side will be longer than the other.
● If either v or y overlaps region 1, then set q to 2. In order to make
the right side match, something would have to be pumped into
region 4. Violates |vxy| k.
● If either v or y overlaps region 2, then set q to 2. In order to make
the right side match, something would have to be pumped into
region 5. Violates |vxy| k.
WcW = {wcw : w {a, b}*}
Variable Declaration and Use
WcW = {wcw : w {a, b}*}.
string winniethepooh;
winniethepooh =
“bearofverylittlebrain”;
Variable Declaration and Use
WcW = {wcw : w {a, b}*}.
string winniethepooh;
winniethepooh =
“bearofverylittlebrain”;
Let J = Java
<prelude> string a*b*;a*b* = “a”;}}.
Prove that J isn’t CF by pumping:
Let w = <prelude> string akbk;akbk = “a”;}}
Is English Context-Free?
If either the man who said it would rain is arriving today or the man who said it wouldn’t rain is not arriving today then we must go.
Cross Serial Dependencies
Chris and the girls runs and swim respectively.
*Chris and the girls runs and swims respectively.
If English is context-free, then so is:
English
{Chris (and (Chris the girls))*
runs (and (run runs))*
respectively}
Each sentence is of the form:
ssverb respectively
What language of a’s and b’s is this similar to?
Swiss German
But English doesn’t really work this way:
● ? Jan and Pat runs and swims, respectively.
● Jan and Pat run and swim, respectively.
But Swiss German does:
Jan säit das mer em Hans es huus hälfed aastriiche.
Jan says that we Hans/DAT the house/ACC helped paint.
Closure Theorems for Context-Free Languages
The context-free languages are closed under:
● Union
● Concatenation
● Kleene star
● Reverse
● Letter substitution
Closure Under Union
Let G1 = (V1, 1, R1, S1), and
G2 = (V2, 2, R2, S2).
Assume that G1 and G2 have disjoint sets of nonterminals,
not including S.
Let L = L(G1) L(G2).
We can show that L is CF by exhibiting a CFG for
it:
Closure Under Union
Let G1 = (V1, 1, R1, S1), and
G2 = (V2, 2, R2, S2).
Assume that G1 and G2 have disjoint sets of nonterminals,
not including S.
Let L = L(G1) L(G2).
We can show that L is CF by exhibiting a CFG for
it:
G = (V1 V2 {S}, 1 2,
R1 R2 {S S1, S S2},
S)
Closure Under Concatenation
Let G1 = (V1, 1, R1, S1), and
G2 = (V2, 2, R2, S2).
Assume that G1 and G2 have disjoint sets of nonterminals,
not including S.
Let L = L(G1)L(G2).
We can show that L is CF by exhibiting a CFG for it:
Closure Under Concatenation
Let G1 = (V1, 1, R1, S1), and
G2 = (V2, 2, R2, S2).
Assume that G1 and G2 have disjoint sets of nonterminals,
not including S.
Let L = L(G1)L(G2).
We can show that L is CF by exhibiting a CFG for it:
G = (V1 V2 {S}, 1 2,
R1 R2 {S S1 S2},
S)
Closure Under Kleene Star
Let G = (V, , R, S1).
Assume that G does not have the nonterminal S.
Let L = L(G)*.
We can show that L is CF by exhibiting a CFG for it:
Closure Under Kleene Star
Let G = (V, , R, S1).
Assume that G does not have the nonterminal S.
Let L = L(G)*.
We can show that L is CF by exhibiting a CFG for it:
G = (V1 {S}, 1,
R1 {S , S S S1},
S)
Closure Under Reverse
LR= {w * : w = xR for some x L}.
Let G = (V, , R, S) be in Chomsky normal form.
Every rule in G is of the form X BC or X a, where X, B, and C are elements of V - and a .
● X a: L(X) = {a}. {a}R = {a}.
● X BC: L(X) = L(B)L(C). (L(B)L(C))R = L(C)RL(B)R.
Construct, from G, a new grammar G, such that L(G) = LR:
G = (VG, G, R, SG), where R is constructed as follows:
● For every rule in G of the form X BC, add to R the rule X CB.
● For every rule in G of the form X a, add to R the rule X a.
What About Intersection and Complement?
Closure under complement implies closure under intersection, since:
L1 L2 = (L1 L2)
But are the CFLs closed under either complement or intersection?
We proved closure for regular languages two different ways:
1. Given a DFSM for L, construct a DFSM for L by swapping accepting and rejecting states. If closed under complement and union, must be closed under intersection.
2. Given automata for L1 and L2, construct an automaton for L1 L2 by simulating the parallel operation of the two original machines,
using states that are the Cartesian product of the sets of states of
the two original machines.
Does either work here?
Closure Under Intersection
The context-free languages are not closed under
intersection:
The proof is by counterexample. Let:
L1 = {anbncm: n, m 0} /* equal a’s and b’s.
L2 = {ambncn: n, m 0} /* equal b’s and c’s.
Both L1 and L2 are context-free, since there exist
straightforward context-free grammars for them.
But now consider:
L = L1 L2
=
Closure Under Intersection
The context-free languages are not closed under
intersection:
The proof is by counterexample. Let:
L1 = {anbncm: n, m 0} /* equal a’s and b’s.
L2 = {ambncn: n, m 0} /* equal b’s and c’s.
Both L1 and L2 are context-free, since there exist
straightforward context-free grammars for them.
But now consider:
L = L1 L2
= {anbncn: n 0}
Closure Under Complement
L1 L2 = (L1 L2)
The context-free languages are closed under union, so if they were closed under complement, they would be closed under intersection (which they are not).
Closure Under Complement
An Example
AnBnCn is context-free:
But (AnBnCn) = AnBnCn is not context-free.
Closure Under Difference
Are the context-free languages closed under difference?
Closure Under Difference
Are the context-free languages closed under difference?
L = * - L.
* is context-free. So, if the context-free languages were closed under difference, the complement of any context-free language would necessarily be context-free. But we just showed that that is not so.
The Intersection of a Context-Free Language and a Regular Language is Context-Free
L = L(M1), a PDA = (K1, , 1, 1, s1, A1).
R = L(M2), a deterministic FSM = (K2, , , s2, A2).
We construct a new PDA, M3, that accepts L R by simulating the parallel execution of M1 and M2.
M = (K1 K2, , 1, , (s1, s2), A1 A2).
Insert into :
For each rule (( q1, a, ), ( p1, )) in 1,
and each rule ( q2, a, p2) in ,
((( q1, q2), a, ), (( p1, p2), )).
For each rule ((q1, , ), (p1, ) in 1,
and each state q2 in K2,
(((q1, q2), , ), ((p1, q2), )).
This works because: we can get away with only one stack.
Theorem: The difference (L1 – L2) between a context-free language L1 and a regular language L2 is context-free.
Proof: L1 – L2 = L1 L2.
If L2 is regular then so is L2.
If L1 is context-free, so is L1 L2.
The Difference between a Context-Free Language and a Regular Language is Context-Free
Let:
L = {anbn: n 0 and n 1776}.
Alternatively:
L = {anbn: n 0} – {a1776b1776}.
{anbn: n 0} is context-free.
{a1776b1776} is regular.
An Example: A Finite Number of Exceptions
One Closure Theorem:
If L1 and L2 are context free, then so is
L3 = L1 L2.
But what if L3 and L1 are context free? What can we say about L2?
L3 = L1 L2.
Don’t Try to Use Closure Backwards
One Closure Theorem:
If L1 and L2 are context free, then so is
L3 = L1 L2.
But what if L3 and L1 are context free? What can we say about L2?
L3 = L1 L2.
Example:
anbnc* = anbnc* anbncn.
Don’t Try to Use Closure Backwards
Using the Closure Theorems with the Pumping Theorem
Let WW = {ww : w {a, b}* }.
Let’s try pumping: Choose w = (ab)2k
(Don’t get confused about the two uses of w.)
w w
ababab…abababababab…ababababab
But this pumps fine with v = and y =
Exploiting Regions
WW = {ww : w {a, b}* }.
Choose the string akbakb.
aaaaa…………………baaaaaa……………..b
w w
But this also pumps fine.
Make All Regions “Long”
WW = {ww : w {a, b}* }.
Choose the string akbkakbk.
aaa….. aabb………bbaa……aabb……..b
w w
1 2 3 4
Now we list the possibilities:
(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 3), (3, 4), (1, 3), (1, 4),
(2, 4), (1/2, 2), (1/2, 3), (1/2, 4), (1/2, 2/3),…
Whenever v or y spans regions, we’ll no longer have a string of the same form, but that’s okay given the definition of L.
Using Intersection with a Regular Language
WW = {ww : w {a, b}* }.
Recall our last choice of w: akbkakbk.
aaa….. aabb………bbaa……aabb……..b
w w
1 2 3 4
But let’s consider L' = L
Using Intersection with a Regular Language
WW = {ww : w {a, b}* }.
But let’s consider L' = L a*b*a*b*.
L' is not context-free. Let w = akbkakbk.
aaa….. aabb………bbaa……aabb……..b
w w
1 2 3 4
Another Example
L = {w : w can be written as
x # y = z :
x, y, z {0, 1}* and, if x, y, and z are
viewed as binary numbers without
leading zeros, xy = zR}.
For example, 100#1111=001111 is in L.
Another Example
L = {w : w can be written as
x # y = z :
x, y, z {0, 1}* and, if x, y, and z are
viewed as binary numbers without
leading zeros, x # y = zR}.
Choose w = 10k#1k=0k1k:
1 000 … 000 # 111 … 111 = 000 … 000111 …111
|1| 2 |3| 4 |5| 6 | 7 |
Note that w is in L.
If L is CF, so is L = L 10*#1*=0*1*:
Another Example
Choose w = 10k#1k=0k1k:
1 000 … 000 # 111 … 111 = 000 … 000111 …111
|1| 2 |3| 4 |5| 6 | 7 |
L = L 10*#1*=0*1* is not CF:
v or y overlaps 1, 3, or 5:
v or y contains the boundary between 6 and 7:
(2, 2), (4, 4), or (2, 4):
(6, 6), (7, 7), or (6, 7):
(4, 6):
(2, 6), (2, 7) or (4, 7):
L = {w {a, b, c}* : #a(w) = #b(w) = #c(w) }
If L were context-free, then L = L a*b*c* would also be context-free.
But L =
So neither is L.
Another Example
L = {w (A-Z, a-z, ., blank)+ : there exists at least one duplicated, capitalized word in w)
A string in L:
The history of China can be viewed from the perspective of an outsider or of someone living in China.
Another Example
L = {w (A-Z, a-z, ., blank)+ : there exists at least one duplicated, capitalized word in w)
Prove not CF by pumping:
Choose w = AakqAak:
Another Example
L = {w (A-Z, a-z, ., blank)+ : there exists at least one duplicated, capitalized word in w)
Prove not CF by pumping:
Choose w = AakbkqkAakbk:
Make it easy: If L is CF, so is L AakbkqAakbk:
Why are the Context-Free Languages Not Closed under Complement, Intersection and Subtraction But the Regular Languages Are?
Given an NDFSM M1, build an FSM M2 such that
L(M2) = L(M1):
1. From M1, construct an equivalent deterministic FSM M,
using ndfsmtodfsm.
2. If M is described with an implied dead state, add the dead state
and all required transitions to it.
3. Begin building M2 by setting it equal to M. Then swap the
accepting and the nonaccepting states. So:
M2 = (KM, , M, sM, KM - AM).
We could do the same thing for CF languages if we could do step 1,
but we can’t.
The need for nondeterminism is the key.
Deterministic PDAs
A PDA M is deterministic iff:
● M contains no pairs of transitions that compete with
each other, and
● Whenever M is in an accepting configuration it has no available moves.
//
M can choose between accepting and taking the
-transition, so it is not deterministic.
Deterministic CFLs
A language L is deterministic context-free iff L$ can be accepted by some deterministic PDA.
Why $?
Let L = a* {anbn : n > 0}.
An NDPDA for L
L = a* {anbn : n > 0}.
A DPDA for L$
L = a* {anbn : n > 0}.
Adding $ Doesn’t Add Power
The Deterministic CF Languages are Closed Under Complement
Given a PDA M, we want to:
● Complete M.
● Swap accepting and nonaccepting configurations.
● Accept (L)$, not L(M).
A deterministic PDA may fail to accept an input string w because:
1. Its computation ends before it finishes reading w.
2. Its computation ends in an accepting state but the stack is not empty.
3. Its computation loops forever, following -transitions, without ever
halting in either an accepting or a nonaccepting state.
4. Its computation ends in a nonaccepting state.
If we simply swap accepting and nonaccepting states we will correctly fail to accept every string that M would have accepted (i.e., every string in L$). But we will not necessarily accept every string in (L)$.
A construction that solves these problems exists.
DCFLs Under Intersection and Union
L1 L2 = (L1 L2).
The DCFLs are closed under complement. What about intersection and union?
DCFLs are Not Closed Under Union
L1 = {aibjck, i, j, k 0 and i j}. (a DCFL)
L2 = {aibjck, i, j, k 0 and j k}. (a DCFL)
L = L1 L2.
= {aibjck, i, j, k 0 and (i j) or (j k)}.
L = L.
= {aibjck, i, j, k 0 and i = j = k}
{w {a, b, c}* : the letters are out of order}.
L = L a*b*c*.
= {anbncn, n 0}.
L is not even CF, much less DCF.
DCFLs are Not Closed Under Intersection
L1 = {aibjck, i, j, k 0 and i = j}.
L2 = {aibjck, i, j, k 0 and j = k}.
L = L1 L2
=
L1 and L2 are deterministic context-free:
Nondeterministic CFLs
Theorem: There exist CLFs that are not deterministic.
Proof: By example. Let L = {aibjck, i j or j k}. L is CF. If L is DCF then so is:
L = L.
= {aibjck, i, j, k 0 and i = j = k}
{w {a, b, c}* : the letters are out of order}.
But then so is:
L = L a*b*c*.
= {anbncn, n 0}.
But it isn’t. So L is context-free but not deterministic context-free.
This simple fact poses a real problem for the designers of efficient context-free parsers.
Inherent Ambiguity vs. Nondeterminism
L1 = {aibjck : i, j, k 0 and (i = j) or (j = k)}.
Alternatively, it is:
{anbncm : n, m 0} {anbmcm : n, m 0}.
L1 is inherently ambiguous. Example:
aabbcc
L2 = {anbncmd : n, m 0} {anbmcme : n, m 0}.
L2 is not inherently ambiguous.
But what should a PDA do on:
aabbccd
Push a’s or not?
The CFL Hierarchy
Ogden’s Lemma
L = {aibicj : i, j 0, i j} is not context-free. We try a pumping proof:
Let w = ak bk ck+k!.
1 | 2 | 3
If either v or y crosses regions, set q to 2. Pump in: out of order.
● (1, 1), (2, 2), (1, 3), (2, 3) Set q to 2. (a’s b’s)
● (1, 2) If |v| |y| then set q to 2. (a’s b’s)
● (1, 2) If |v| = |y| then set q to (k!/|v|) + 1. (k!/|v|) must be an integer
since |v| k. The string that results from pumping is aXbXck+k!,
where:
X = k + (q – 1)|v|
= k + (k!/|v|)|v|
= k + k!.
So far, so good. But what about (3, 3)?
Ogden’s Lemma
L = {aibicj : i, j 0, i j} is not context-free. We try a pumping proof:
Let w = ak bk ck+k!.
1 | 2| 3
● (3, 3)
- Pumping in: will result in even more c’s than a’s and b’s. So the resulting string is in L.
- Pumping out: the maximum number of c’s that can be pumped out is k, which would result in a string with k! c’s. But, as long as k 3,
k! > k. So the resulting string is in L.
We’re stuck.
Ogden’s Lemma
We mark some symbols as distinguished and require that at least one of v or y contain at least one marked symbol.
Ogden’s Lemma
Theorem: If L is a context-free language, then:
k 1
( strings w L, where |w| k, if we mark at
least k symbols of w as distinguished then:
(u, v, x, y, z (w = uvxyz and
vy contains at least one distinguished symbol,
vxy contains at most k distinguished
symbols, and
q 0 (uvqxyqz is in L)))).
Proof: The proof is analogous to the one we did for the context-free Pumping Theorem except that we consider only paths that generate the distinguished symbols.
Using Ogden’s Lemma
L = {aibicj : i, j 0, i j} is not context-free. Let w = akbkck+k!. Mark all the a’s in w as distinguished. If either v or y contains two or more distinct symbols, then set q to 2. The resulting string will have letters out of order and thus not be in L. We consider the remaining possibilities:
● (1, 1) (1, 3): Set q to 2. The number of a’s will no longer equal the number of b’s, so the resulting string is not in L.
● (1, 2): Same argument as above.
● (2, 2), (2, 3), (3, 3): fail to satisfy the requirement that at least one symbol in vy be marked as distinguished.
There is no way to divide w into vxy such that all the conditions of Ogden’s Lemma are met. So L is not context-free.
Letter Equivalence
Two languages L1 and L2 are letter-equivalent iff they contain the same strings if we disregard the order in which the symbols occur in the strings.
Example:
(ab)* is letter equivalent to: (ba)*
{anbn: n 0}
Letter Equivalence
Define: (w) = (i1, i2, … ik).
Example: if = {a, b, c, d},
then (aabbbbddd) = (2, 4, 0, 3).
Define: (L) =
{(i1, i2, … ik) : w L ((w) = (i1, i2, … ik))}
Two languages L1 and L2 are letter-equivalent iff:
(L1) = (L2).
Examples of Letter Equivalence
Let = {a, b}. Then: (a) = (1, 0).
(aaabbbb) = (3, 4).
Now consider :
● L1 = AnBn = {anbn : n 0} (L1) = {(i, i) : 0 i}.
● L2 = (ab)* (L2) = {(i, i) : 0 i}.
● L3 = {anbnan : n 0} (L3) = {(2i, i) : 0 i}.
● L4 = {a2nbn : n 0} (L4) ={(2i, i) : 0 i}.
● L5 = (aba)* (L5) = {(2i, i) : 0 i}.
L1 and L2 are letter-equivalent. So are L3, L4 and L5.
Parikh’s Theorem
Theorem: Every context-free language is letter-equivalent to some regular language.
Proof: By an argument similar to the one used to prove the Pumping Theorem.
Context-Free Languages Over
a Single-Letter Alphabet
Theorem: Any context-free language over a single-letter alphabet is regular.
Proof: Follows from Parikh’s Theorem
Examples:
L = {anbn}.
L = {anan}.
=
L = {wwR : w {a, b}*}.
L = {wwR : w {a}*}.
=
L = {anbm : n, m 0 and n m}.
L = {anam : n, m 0 and n m}.
=
Using The Corollary
Primea = {an : n is prime}.
Primea is not context-free. If it were, then it would also be regular. But we showed that it is not regular.
So it is not context-free either.
Functions on Context-Free Languages
Are the context-free languages closed under:
firstchars(L) =
{w : yL (y = cx c L x L* w c*)}.
Functions on Context-Free Languages
Are the context-free languages closed under
maxstring(L) =
{w: w L and z * (z wz L)}.
Functions on Context-Free Languages
Are the context-free languages closed under
maxstring(L) =
{w: w L and z * (z wz L)}.
Consider L = {aibjck : k i or k j}.
p
k
a
+
4
a
n
2
4
k
a
4
k
a
