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?

  • 3
    $\begingroup$ Are you asking whether for any context-free language $L$, the language $L^*$ is always deterministic context-free? If not, please clarify your question. $\endgroup$ Sep 11, 2015 at 12:45
  • $\begingroup$ 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 $\endgroup$ Sep 11, 2015 at 12:50
  • $\begingroup$ 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^* \}$? $\endgroup$ Sep 11, 2015 at 14:50
  • 2
    $\begingroup$ OK. I suggest you edit the question to say that -- I too found it hard to understand what you are asking. $\endgroup$
    – D.W.
    Sep 11, 2015 at 15:35
  • 1
    $\begingroup$ Your language is probably not deterministic context-free (if I had to guess), but this is probably messy to prove. $\endgroup$ Sep 12, 2015 at 7:37


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.