Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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\}^*$.

share|improve this question

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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