I am looking for a proof for the following problem:

For languages $L$ and $R$, if $L$ is deterministic context-free and $R$ is regular, then $LR$ is a deterministic context-free language.

Note: $RL$ may not satisfy this condition, e.g. if $L=\{wcw^R\mid w\in (a|b)^*\}$, and $R=\{a\}^*$.


1 Answer 1


Here is an idea. You have to work out the details by your own.

Let $Q_R$ be the states of a DEA accepting $R$, and let $Q_L$ be the states of a deterministic PDA accepting $L$. You build now a new deterministic PDA $P$ that accepts $LR$ as follows:

The state space of $P$ is $Q'=Q_L\times \mathcal{P}(Q_R)$. If you have read $w$ and you are with $P$ in state $(s,T)$, this tells you the following: $L$ would be in state $s$ after reading $w$, and for every $t\in T$ there was a possibility that a prefix of $w$ was in $L$, and the remaining suffix of $w$ would have send the DEA for $R$ to state $t$. You accept if you are in a state $(s,T)$, that contains an accepting DEA-state in $T$. The transitions can be worked out straight-forward. Notice that it might be helpful to modify the PDA for $L$ first, such that it has a total transition function. You can achieve this easily by adding a non-accepting dummy states, that collects all missing transitions.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.