# Linear time parsing from star of context free language

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|A
A -> aAa|bAb|e


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.

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?

• Are you asking whether for any context-free language $L$, the language $L^*$ is always deterministic context-free? If not, please clarify your question. – Yuval Filmus Sep 11 '15 at 12:45
• No, I am asking if it is possible in general that this happens (not always, but in particular cases) and specifically I thought of this example to understand better. I am sorry, I did not express myself in a clear way – Giulia Frascaria Sep 11 '15 at 12:50
• So are you asking either or both of the following questions? (1) Is there a context-free language $L$ which is not deterministic context-free such that $L^*$ is deterministic context-free? (2) Is $L^*$ deterministic context-free, where $L = \{ xx^R : x \in \Sigma^* \}$? – Yuval Filmus Sep 11 '15 at 14:50
• OK. I suggest you edit the question to say that -- I too found it hard to understand what you are asking. – D.W. Sep 11 '15 at 15:35
• Your language is probably not deterministic context-free (if I had to guess), but this is probably messy to prove. – Yuval Filmus Sep 12 '15 at 7:37