Look-ahead on pushdowns (Q579952): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
The general notion of look-ahead on pushdowns is used to prove that (1) the deterministic iterated pushdown languages are closed under complementation, (2) the deterministic iterated pushdown languages are properly included in the nondeterministic iterated pushdown languages; the counter example is a very simple linear context-free language, independent of the amount of iteration, (3) LL(k) iterated indexed grammars can be parsed by deterministic iterated pushdown automata, and (4) it is decidable whether an iterated indexed grammar is LL(k). Analogous results hold for iterated pushdown automata with regular look- ahead on the input, and LL-regular iterated indexed grammars. | |||
Property / review text: The general notion of look-ahead on pushdowns is used to prove that (1) the deterministic iterated pushdown languages are closed under complementation, (2) the deterministic iterated pushdown languages are properly included in the nondeterministic iterated pushdown languages; the counter example is a very simple linear context-free language, independent of the amount of iteration, (3) LL(k) iterated indexed grammars can be parsed by deterministic iterated pushdown automata, and (4) it is decidable whether an iterated indexed grammar is LL(k). Analogous results hold for iterated pushdown automata with regular look- ahead on the input, and LL-regular iterated indexed grammars. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q45 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68N20 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 4016221 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
look-ahead on pushdowns | |||
Property / zbMATH Keywords: look-ahead on pushdowns / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
iterated pushdown languages | |||
Property / zbMATH Keywords: iterated pushdown languages / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
LL(k) iterated indexed grammars | |||
Property / zbMATH Keywords: LL(k) iterated indexed grammars / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
iterated pushdown automata | |||
Property / zbMATH Keywords: iterated pushdown automata / rank | |||
Normal rank |
Revision as of 17:33, 1 July 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Look-ahead on pushdowns |
scientific article |
Statements
Look-ahead on pushdowns (English)
0 references
1987
0 references
The general notion of look-ahead on pushdowns is used to prove that (1) the deterministic iterated pushdown languages are closed under complementation, (2) the deterministic iterated pushdown languages are properly included in the nondeterministic iterated pushdown languages; the counter example is a very simple linear context-free language, independent of the amount of iteration, (3) LL(k) iterated indexed grammars can be parsed by deterministic iterated pushdown automata, and (4) it is decidable whether an iterated indexed grammar is LL(k). Analogous results hold for iterated pushdown automata with regular look- ahead on the input, and LL-regular iterated indexed grammars.
0 references
look-ahead on pushdowns
0 references
iterated pushdown languages
0 references
LL(k) iterated indexed grammars
0 references
iterated pushdown automata
0 references