Simulating finite automata with context-free grammars. (Q1853167): Difference between revisions
From MaRDI portal
Created claim: Wikidata QID (P12): Q61677530, #quickstatements; #temporary_batch_1706389175803 |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Jeffrey O. Shallit / rank | |||
Property / author | |||
Property / author: Jeffrey O. Shallit / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Tight lower bounds on the length of word chains / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the length of word chains / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Intersection and union of regular languages and state complexity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Finite automata and unary languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4939575 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5834367 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A pushdown automaton or a context-free grammar - which is more economical? / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Normal Recurring Decimals / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5541336 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some classifications of context-free languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4105792 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5592246 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4531381 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The state complexities of some basic operations on regular languages / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 11:23, 5 June 2024
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
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