Define the operation SUFFIX on languages as follows SUFFIXA

Define the operation SUFFIX on languages as follows:

SUFFIX(A) = { v | uv A for some string u}.

Show that the class of context-free languages is closed under the SUFFIX operation.

Hint: Try to obtain a pushdown automaton M for SUFFIX(A) from a pushdown automaton M\' for A. The machine M will have to do what M\' does on string u, only it will do it without consuming any input; another way to think of this is that M is imagining that the input began with u. After this, M will behave exactly like M\', i.e. it will also consume the input. If you follow this suggestion, you should present the 6-tuple for M based on the one for M\' and you should explain how your construction captures the described intuition.

Solution

For every state A, add a state A. And new start state will be S. For every transition (A,0,a) (B,b) add a transition (A,,a) (B,b). And (A,,) (A,).

OR

>Let A be a context-free language. We show that SUFFIX ( A ) is also a CFL. Let M = ( Q, , ,,q 0 ,F ) be a PDA that recognizes A . We show how to use M to construct a PDA N that recognizes SUFFIX ( A ) . On an input string v , our PDA N must determine if there exists another string u such that uv is in A . The key idea is that N contains two copies of M , although one copy is modied. The rst copy of M is modied so that it does not read any symbols of input; the effect is that this modied copy of M nondeterministically guesses a prex string u and manipulates the stack as though M were reading u . After pretending to read u , the PDA N then -transitions to the second copy of M which actually does read the input v . Our PDA N accepts if the second copy of M accept
Formally, we dene N = ( Q N , , , N ,q N ,F N ) as follows

(a) Q N = Q × { U-PART , V-PART

(b) N (( p, U-PART ) ,,b ) = { (( q, U-PART ) ,c ) | for some a , ( q,c ) ( p,a,b ) } b N (( p, U-PART ) ,, ) = { (( q, U-PART ) ,c ) | for some a , ( q,c ) ( p,a, ) } { (( p, V-PART ) , ) } N (( p, V-PART ) ,a,b ) = { (( q, V-PART ) ,c ) | ( q,c ) ( p,a,b ) } a , b
(c) q N = ( q 0 , U-PART )
(d) F N = { ( q, V-PART ) | q F } = F × { V-PART}
In fact, the conclusion holds as long as G generates a string of length more than 2 b - 1