Ogden's lemma

Encyclopedia : O : OG : OGD : Ogden's lemma

---

---

 

In the theory of formal languages, Ogden's lemma provides an extension of flexibility over the pumping lemma for context-free languages.

Ogden's lemma states that if a language L is context-free, then there exists some number p > 0 (where p may or may not be a pumping length) such that for any string w in L, we can mark p or more of the positions in w as "distinguished"; then w can be written as

w = uvxyz

with strings u, v, x, y and z, such that v and y have at least one distinguished position between them, vxy has at most p distinguished positions, and

uv ⁱxy ⁱz is in L for every i ≥ 0.

Note that this is trivially true if the language is not infinite, since then p just needs to be longer than longest string in the language.

Ogden's lemma can be used to show that certain languages are not context-free, in cases where the pumping lemma for context-free languages is not sufficient. Observe that when every position is marked as distinguished, this lemma is equivalent to the pumping lemma for context-free languages.

See also

• Pumping lemma for context-free languages

References

 

---

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.

---

Search Titles

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

?