Simulating finite automata with context-free grammars. (Q1853167)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Simulating finite automata with context-free grammars.
scientific article

    Statements

    Simulating finite automata with context-free grammars. (English)
    0 references
    0 references
    0 references
    0 references
    21 January 2003
    0 references
    We consider simulating finite automata (both deterministic and nondeterministic) with context-free grammars in Chomsky Normal Form (CNF). We show that any unary DFA with \(n\) states can be simulated by a CNF grammar with \(O(n^{1/3})\) variables, and this bound is tight. We show that any unary NFA with \(n\) states can be simulated by a CNF grammar with \(O(n^{2/3})\) variables. Finally, for larger alphabets we show that there exist languages which can be accepted by an \(n\)-state DFA, but which require \(\Omega(n/\log n)\) variables in any equivalent CNF grammar.
    0 references
    Formal languages
    0 references
    Context-free grammar
    0 references
    Finite automata
    0 references

    Identifiers