Geek asks and answers

Using Ogden's lemma compared to the usual pumping lemma for non-contextual grammar grammars

I am studying the difference between the lemma in the question. Each link I can find uses an example:

{(a^i)(b^j)(c^k)(d^l) : i = 0 or j = k = l}

to show the difference between the two. I can find an example using the usual lemma to “refute” it.

Choose w = uvxyz, st | vy | > 0, | vxy | <= p. Suppose that w contains an equal number b, c, d s.

I chose:

u,v,x = ε
y = (the string of a's)
z = (the rest of the string w)

Pumping y will simply add a to the number, and if | b | = | c | = | d | at first it will still be.

(A similar argument if w does not have a. Then just download whatever you want.)

My question is, how does Ogden's Lemma change this strategy? What does “labeling” do?

Thank!

+7
source
2

, " " , , " " , . , , , , , ...

Grammar context free        => Pumping Lemma is definitely satisfied  
Grammar not context free    => Pumping Lemma *may* be satisfied
Pumping Lemma satisfied     => Grammar *may* be context free
Pumping Lemma not satisfied => Grammar definitely not context free
# (we can write exactly the same for Ogden Lemma)
# Here "=>" should be read as implies

, , , , (!) . ( , , .)

, L = { a^i b^j c^k d^l where i = 0 or j = k = l} ( , ):

:

L , p ≥ 1 , s L |s| ≥ p ( p - ) s = uvxyz
u, v, x, y and z, , : 1. |vxy| ≤ p,
2. |vy| ≥ 1
3. u v^n x y^n z L n.

:

s L ( |s|>=p):

  • s a, v=a, x=epsilon, y=epsilon ( , ).
  • s a (w=b^j c^k d^l j, k L , |s|>=1), v=b (if j>0, v=c elif k>0, else v=c), x=epsilon, y=epsilon ( , ).

( : , , L!
: , .)

:

L , p > 0 ( p ), w p L "" p w, w w = uxyzv
u, x, y, z, v , :
1. xz ,
2. xyz p
3. u x^n y z^n v L n ≥ 0.

: , : " " ", p.

:

w = a b^p c^p d^p b ( p, w ), u,x,y,z,v - , (z=uxyzv).

  • x z , u x^2 y z^2 w L, ( (bc)^2 = bcbc).
  • x, z b ( 1).

( i,j>0):

  • x=epsilon, z=b^i
  • x=a, z=b^i
  • x=b^i, z=c^j
  • x=b^i, z=d^j
  • x=b^i, z=epsilon

( b s, c d s), , u x^2 v y^2 z L ( (!), , , L -).

.

, L -, ( ) , , , :

, - .

+13

, , "" . , , , uvxyz. " ", , uvxyz.

0

More articles:


All Articles