Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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\}^*$.
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.
