91Ó°ÊÓ

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).$

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

For every transition

$\mathrm{δ}\left(A,0,a\right)→\left(B,b\right)$

Add a transition

$\mathrm{δ}\left(A\text{'},\mathrm{Î\mu },a\right)→\left(B\text{'},b\right).And\mathrm{δ}\left(A\text{'},\mathrm{Î\mu },\mathrm{Î\mu }\right)→\left(A,\mathrm{Î\mu }\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→cisreplacedwith\mathrm{Î\mu },b→c.$

Here add the transition

$\mathrm{Î\mu },\mathrm{Î\mu }→\mathrm{Î\mu },$

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

$\mathrm{Î\mu },\mathrm{Î\mu }→\mathrm{Î\mu },$

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.