Linear time parsing from star of context free language - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T03:08:40Z https://cs.stackexchange.com/feeds/question/47069 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/47069 0 Linear time parsing from star of context free language Giulia Frascaria https://cs.stackexchange.com/users/37986 2015-09-11T07:55:48Z 2015-09-11T17:47:33Z <p>I was wondering if there are cases in which the star closure of a language can make the resulting language easier to parse. In particular, if I have this grammar:</p> <pre><code>S -&gt; c|AS|A A -&gt; aAa|bAb|e </code></pre> <p>I can see that $L(A) = \{x x^R : x \in \Sigma^*\}$ (where $x^R$ denotes the reverse of $x$). That language is not even deterministic context free since I can't determine where the switch from $x$ to $x^R$ happens looking at the top of the stack only.</p> <p>Using Arden's rule, I noticed that $L(S) = L(A)^* c + L(A)^*$. So, is it possible to parse $L(S)$ without nondeterminism? I thought that a string $w$ like $aaabbaaa$ could be seen, in $L(S)$, as a concatenation of $w_1 w_2 w_3$ where $w_1 = aa$, $w_2 = abba$, $w_3 = aa$. As for this word in particular, an automaton could recognize and accept the strings by inspecting only one stack symbol at a time. Could this be generalized in some way for the whole language $L(S)$ of the example?</p> <p>In particular, is $L(A)^*$ a deterministic context-free language? Can it be accepted by a deterministic pushdown automaton?</p>