[SOLVED] 代写 C theory EECS2001:

EECS2001:
Introduction to Theory of Computation
Summer 2019
Ali Mahmoodi
[email protected]
Office: Lassonde 2015 Course page: Moodle
Notes based on work by Professor Suprakash Datta
6/19/2019 EECS2001, Summer 2019 1

Next
• Non-CF languages
• CFL pumping lemma
6/19/2019 EECS2001, Summer 2019 2

Non-CF Languages
The language L = { anbncn | n0 } does not appear to be context-free.
Informal: The problem is that every variable can (only) act ‘by itself’ (context-free).
The problem of A * vAy :
If S * uAz * uvAyz * uvxyz  L,
then S * uAz * uvAyz * … * uviAyiz
* uvixyiz  L as well, for all i=0,1,2,… 6/19/2019 EECS2001, Summer 2019 3

“Pumping Lemma for CFLs”
Idea: If we can prove the existence of derivations for elements of the CFL L that use the step
A * vAy, then a new form of ‘v-y pumping’ holds: A * vAy * v2Ay2 * v3Ay3 * …)
Observation: We can prove this existence if the parse-tree is tall enough.
6/19/2019 EECS2001, Summer 2019 4

Remember Parse Trees
Parse tree for S  AbbcBa * cbbccccaBca
S
 cbbccccacca
Abb
cBa c
A
cc
cc
aBc
6/19/2019
EECS2001, Summer 2019 5

Pumping a Parse Tree
S
A
A
uvxyz
If s = uvxyz  L is long, then its parse-tree is tall.
Hence, there is a path on which a variable A
repeats itself. We can pump this A–A part.
6/19/2019 EECS2001, Summer 2019 6

A Tree Tall Enough
Let L be a context-free language, and let G be its grammar with maximal b symbols on the right side of the rules: A → X1…Xb
A parse tree of height h produces a string with maximum length of bh.
Long strings implies tall trees.
Let |V| be the number of variables of G.
If h = |V|+1 or bigger, then there is a variable on a ‘top-down path’ that occurs more than once.
6/19/2019 EECS2001, Summer 2019 7

uvxyz L S
A A
uvxyz
By repeating the A–A part we get…
6/19/2019 EECS2001, Summer 2019 8

uv2xy2z L S
A
A
A uvxRyz
y
… while removing the A–-A gives…
vx
6/19/2019 EECS2001, Summer 2019 9

Pumping down: uxz  L S
A
x
uz
In general uvixyiz  L for all i=0,1,2,…
6/19/2019 EECS2001, Summer 2019 10

Pumping Lemma for CFL
For every context-free language L, there is a pumping length p, such that for every string sL and |s|p, we can write s=uvxyz with
1) uvixyiz  L for every i{0,1,2,…} 2) |vy|  1
3) |vxy|  p
Note that 1) implies that uxz  L
2) says that vy cannot be the empty string  Condition 3) is not always used
6/19/2019 EECS2001, Summer 2019 11

Formal Proof of Pumping Lemma
Let G=(V,,R,S) be the grammar of a CFL. Maximum size of rules is b2: A → X1…Xb
A string s requires a minimum height  logb|s|. If |s|  p=b|V|+1, then tree-height  |V|+1, hence there is a path with |V| +2 nodes on it and a variable A must repeat itself:
S * uAz * uvAyz * uvxyz
It follows that uvixyiz  L for all i=0,1,2,… Furthermore:
|vy|  1 because tree is minimal
|vxy|  p because bottom tree with  p leaves
has a ‘repeating path’
6/19/2019 EECS2001, Summer 2019 12

Pumping anbncn (Ex. 2.20)
Assume that B = {anbncn | n0} is CFL
Let p be the pumping length, and s = apbpcp  B P.L.: s = uvxyz = apbpcp, with uvixyiz  B for all i0 Options for |vxy|:
1) The strings v and y are uniform
(v=a…a and y=c…c, for example).
Then uv2xy2z will not contain the same number of a’s, b’s and c’s, hence uv2xy2zB
2) v and y are not uniform.
Then uv2xy2z will not be a…ab…bc…c Hence uv2xy2zB
6/19/2019 EECS2001, Summer 2019 13

Pumping anbncn (cont.)
Assume that B = {anbncn | n0} is CFL
Let p be the pumping length, and s = apbpcp  B P.L.: s = uvxyz = apbpcp, with uvixyiz  B for all i0
We showed: No options for |vxy| such that uvixyiz  B for all i. Contradiction.
B is not a context-free language.
6/19/2019 EECS2001, Summer 2019 14

Example 2.21 (Pumping down)
Proof that C = {aibjck | 0ijk } is not context-free. Let p be the pumping length, and s = apbpcp  C P.L.: s = uvxyz, such that uvixyiz  C for every i0 Two options for 1  |vxy|  p:
1) vxy = a*b*, then the string uv2xy2z has not enough c’s, hence uv2xy2zC
2) vxy = b*c*, then the string uv0xy0z = uxz has too many a’s, hence uv0xy0zC
Contradiction: C is not a context-free language.
6/19/2019 EECS2001, Summer 2019 15

D = { ww | w{0,1}* } (Ex. 2.22)
Carefully take the strings sD.
Let p be the pumping length, take s=0p1p0p1p. Three options for s=uvxyz with 1  |vxy|  p: 1) If a part of y is to the left of | in 0p1p|0p1p,
then second half of uv2xy2z starts with “1” 2) Same reasoning if a part of v is to the right
of middle of 0p1p|0p1p, hence uv2xy2z  D 3) If x is in the middle of 0p1p|0p1p, then uxz
equals 0p1i 0j1p  D (because i or j < p)Contradiction: D is not context-free. 6/19/2019 EECS2001, Summer 2019 16 Pumping ProblemsUsing the CFL pumping lemma is more difficult than the pumping lemma for regular languages.You have to choose the string s carefully, and divide the options efficiently.Additional CFL properties would be helpful (like we had for regular languages).What about closure under standard operations?6/19/2019 EECS2001, Summer 2019 17 Next• Closure properties of CFL6/19/2019 EECS2001, Summer 2019 18 Union Closure PropertiesLemma: Let A1 and A2 be two CF languages, then the union A1A2 is context free as well.Proof: Assume that the two grammars are G1=(V1,,R1,S1) and G2=(V2,,R2,S2). Construct a third grammar G3=(V3,,R3,S3) by:V3 = V1 V2  { S3 } (new start variable) with R3 = R1  R2  { S3 → S1 | S2 }.It follows that L(G3) = L(G1)  L(G2).6/19/2019 EECS2001, Summer 2019 19 Intersection & Complement?Let again A1 and A2 be two CF languages.One can prove that, in general, the intersection A1  A2 ,andthe complement Ā1= * A1are not context free languages.One proves this with specific counter examples of languages. 6/19/2019 EECS2001, Summer 2019 20 What do we really know?Can we always decide if a language L is regular/ context-free or not?We know:{ 1x | x = 0 mod 7 } is regular{ 1x | x is prime } is not regularBut what about{ 1x | x and x+2 are prime }?This is (yet) unknown.6/19/2019 EECS2001, Summer 2019 21 Describing a LanguageThe problem lies in the informal notion of a description.Consider:{ n | a,b,c: an+bn = cn }{ x | in year x the first female US president } { x | x is “an easy to remember number” } We have to define what we mean by “description” and “method of deciding”.6/19/2019 EECS2001, Summer 2019 22