A graph-based regularity test for deterministic context-free languages (Q1177178): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
| links / mardi / name | links / mardi / name | ||
Revision as of 23:46, 29 January 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A graph-based regularity test for deterministic context-free languages |
scientific article |
Statements
A graph-based regularity test for deterministic context-free languages (English)
0 references
26 June 1992
0 references
It is shown that there exists a test of complexity \(O((qt)^ 2 t^{qt})\) for testing the regularity of a deterministic context-free language, where \(q\) is the number of states and \(t\) is the stack alphabet size of the pushdown automaton derived from an \(LR(1)\) grammar for the languages. The previously established upper bound for the test was \(t^{q^ q}\).
0 references
context-free languages
0 references
pushdown automata
0 references
