A graph-based regularity test for deterministic context-free languages

DOI10.1016/0304-3975(91)90076-EMaRDI QIDQ1177178zbMATH OpenFDO

Authors Priti Shankar, B. S. Adiga

Publication date 26 June 1992

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(91)90076-E

zbMATH Keywords

context-free languagespushdown automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Review text

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}\).

Recommendations

• Polynomial size test sets for context-free languages
• Polynomial size test sets for context-free languages
• Efficient constructions of test sets for regular and context-free languages

Cites work

• A regularity test for pushdown machines
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 4189193 (Why is no real title available?)
• Regularity and Related Problems for Deterministic Pushdown Automata

Cited in

(8)

• Amalgams of finite inverse semigroups and deterministic context-free languages.
• Set of memories of a D-graph
• A REGULARITY CONDITION FOR CONTEXT-FREE GRAMMARS
• scientific article; zbMATH DE number 177455 (Why is no real title available?)
• Squares of regular languages
• scientific article; zbMATH DE number 7453188 (Why is no real title available?)
• Regular languages viewed from a graph-theoretic perspective
• Polynomial size test sets for context-free languages

This page was built for publication: A graph-based regularity test for deterministic context-free languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1177178)