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:S -> c|AS|AA -> aAa|bAb|eI 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.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?In particular, is $L(A)^*$ a deterministic context-free language?  Can it be accepted by a deterministic pushdown automaton?
Linear time parsing from star of context free language
formal languages;formal grammars;pushdown automata;parsers