Question

For any language, let SUFFIX() =$\mathbf{\left\{}\mathit{v}\mathbf{\right|}\mathit{u}\mathit{v}\mathbf{\in }\mathit{A}\mathbf{}\mathit{f}\mathit{o}\mathit{r}\mathbf{}\mathit{s}\mathit{o}\mathit{m}\mathit{e}\mathbf{}\mathit{s}\mathit{t}\mathit{r}\mathit{i}\mathit{n}\mathit{g}\mathbf{}\mathit{u}\mathbf{\}}\mathbf{.}$ Show that the class of context-free languages is closed under the SUFFIX operation

Short answer

It is shown that the set of context-free languages is closed under the SUFFIX operation

Step-by-step solution

Define context-free languages

The context-free language is generated by context-free grammar.

These languages are accepted by Pushdown Automata. These are the supersets of regular languages.

Consider context-free languages$L_1$ described as $G_1=(V_1,S,R_1,S_1).$

Consider context-free language$L_2$ described as$G_2=(V_2,S,R_2,S_2).$

Explain how context-free languages are closed under the SUFFIX operation

For every state $A$, add a state $A^{\text{'}}$. The new start state will be $S^{\text{'}}$.

For every transition

$\delta \left(A,0,a\right)\to \left(B,b\right)$

Add a transition

$\delta \left(A\text{'},\epsilon ,a\right)\to \left(B\text{'},b\right).And\delta \left(A\text{'},\epsilon ,\epsilon \right)\to \left(A,\epsilon \right).$

Let be a context-free language recognized by the pushdown deterministic automata . We are going to construct a pushdown deterministic automata$M_1$recognizing the language SUFFIX ($A$) to show that the language SUFFIX ($A$) is also context-free.

Let$M_2$be identical to $M_1$. Here update the transitions of$M_2$so that the transitions are performed without consuming any input symbol.

That is, any transition of the form

$a,b\to cisreplacedwith\epsilon ,b\to c.$

Here add the transition

$\epsilon ,\epsilon \to \epsilon ,$

from each state in$M_2$ to the corresponding state in $M_1$.$M_1$ and$M_2$ together form the pushdown deterministic automata $M$.

Start state of$M$ is the start state of $M_2$. When M starts reading a string v, it will construct the stack as it was reading u without reading u and without consuming any input symbol. This is possible since we updated all transitions in$M_2$ accordingly. Then at some point, by following the transition

$\epsilon ,\epsilon \to \epsilon ,$

The computation continues in$M_1$ by reading the string $v$.

So, the only accepted strings are those which are the suffixes of the strings in $A$. We conclude that the set of context-free languages is closed under the SUFFIX operation.