A pumping lemma for real-time deterministic context-free languages (Q1081309): Difference between revisions

We establish a pumping lemma for real-time deterministic context-free languages. The pumping lemma is useful to prove that a given deterministic context-free language is not real-time. The proving scheme by the pumping lemma is shown by a number of examples.

0 references

Mathematics Subject Classification ID

68Q45

0 references

zbMATH DE Number

3970125

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/0304-3975(85)90032-5

0 references

0 references

0 references

A Generalization of Ogden's Lemma

0 references

Two iteration theorems for the LL(k) languages

0 references

Two iteration theorems for some families of languages

0 references

Deterministic context free languages

0 references

Q4198075

0 references

Real-Time Strict Deterministic Languages

0 references

Strict deterministic grammars

0 references

On the Parsing of Deterministic Languages

0 references

Q5592246

0 references

Q4181301

0 references

Iteration theorems for families of strict deterministic languages

0 references

Q4072875

0 references

Q3948610

0 references

A helpful result for proving inherent ambiguity

0 references

Q3680301

0 references

A strong pumping lemma for context-free languages

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1081309

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0304-3975(85)90032-5
+Normal rank
@@ Property / OpenAlex ID @@
+W1987687368
@@ Property / OpenAlex ID: W1987687368 / rank @@
+Normal rank
@@ Property / Wikidata QID @@
+Q124841187
@@ Property / Wikidata QID: Q124841187 / rank @@
+Normal rank
@@ Property / cites work @@
+A Generalization of Ogden's Lemma
@@ Property / cites work: A Generalization of Ogden's Lemma / rank @@
+Normal rank
@@ Property / cites work @@
+Two iteration theorems for the LL(k) languages
@@ Property / cites work: Two iteration theorems for the LL(k) languages / rank @@
+Normal rank
@@ Property / cites work @@
+Two iteration theorems for some families of languages
+Normal rank
@@ Property / cites work @@
+Deterministic context free languages
@@ Property / cites work: Deterministic context free languages / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198075
@@ Property / cites work: Q4198075 / rank @@
+Normal rank
@@ Property / cites work @@
+Real-Time Strict Deterministic Languages
@@ Property / cites work: Real-Time Strict Deterministic Languages / rank @@
+Normal rank
@@ Property / cites work @@
+Strict deterministic grammars
@@ Property / cites work: Strict deterministic grammars / rank @@
+Normal rank
@@ Property / cites work @@
+On the Parsing of Deterministic Languages
@@ Property / cites work: On the Parsing of Deterministic Languages / rank @@
+Normal rank
@@ Property / cites work @@
+Q5592246
@@ Property / cites work: Q5592246 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4181301
@@ Property / cites work: Q4181301 / rank @@
+Normal rank
@@ Property / cites work @@
+Iteration theorems for families of strict deterministic languages
+Normal rank
@@ Property / cites work @@
+Q4072875
@@ Property / cites work: Q4072875 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3948610
@@ Property / cites work: Q3948610 / rank @@
+Normal rank
@@ Property / cites work @@
+A helpful result for proving inherent ambiguity
@@ Property / cites work: A helpful result for proving inherent ambiguity / rank @@
+Normal rank
@@ Property / cites work @@
+Q3680301
@@ Property / cites work: Q3680301 / rank @@
+Normal rank
@@ Property / cites work @@
+A strong pumping lemma for context-free languages
@@ Property / cites work: A strong pumping lemma for context-free languages / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:1081309