All Questions
Tagged with context-free time-complexity
3 questions
3
votes
0
answers
101
views
Time complexity of context-free languages
I am reading an old paper [1] about time complexity of context-free languages. The computational model is the standard one-tape Turing machine. It is written on page 377 without a proof that "we ...
- 303
8
votes
0
answers
1k
views
Is there an ambiguity test for CFGs faster than trying all strings?
It is well known that testing whether a grammar is ambiguous is undecidable. It is however trivially decidable for any $G$ whether $L_n(G) := \{ w | w \in L(G) \wedge |w| \leq n \}$ for any $n \in \...
- 4,730
23
votes
1
answer
2k
views
Can all unambiguous grammars be parsed in linear time?
When tinkering with noncanonical LR parsing, I thought up a parsing method (with infinitely sized tables, which makes it somewhat unpractical) capable of parsing exactly the unambiguous grammars in $O(...
- 4,730