Question

Prove that the following language is context-free: L = { ω#x | ω^R is a substring of x and x, w ∈ {0,1}* } where ω^R is ω reversed.

Answer 1

QUESTION:

Prove that the following language is context-free: L = { ω#x | ω^R is a substring of x and x, w ∈ {0,1}* } where ω^R is ω reversed.

ANSWER:

Definition - A context-free grammar (CFG) consisting of a finite set of grammar rules is a quadruple (V, T, P, S) where

• V is a final set of non-terminal symbols.

• T is a set of terminals where N ∩ T = NULL.

• P is a set of rules or productions, P: N → (N ∪ T)*, i.e., the left-hand side of the production rule P does have any right context or left context.

• S is the start symbol.

Coming to the question, Given language L = { ω # x | ω^R is a substring of x and x, w ∈ {0,1}* }. [ where ω^R is ω reversed ]

Here x in ω # x contains ω^R as a substring in it so we can write x as a ω^R b  where ω, a, b ∈ {0,1}*.

All the strings in this language share the property that they start with a string ω followed by #,
followed by anything (0,1)* , followed by ω^R, followed by anything (0,1)* . So we want strings of the form : ω # a ω^R b where ω, a, b ∈ {0,1}* and ω^R is ω reversed .

more general form after eliminating a, b∈ {0,1}* would be ω # (0,1)* ω^R (0,1)* where ω^R is ω reversed.

Now for proving the given language is Context-free, we try to construct CFG productions....

Let A generate the ω # (0,1)* ω^R  part, and let B generate final (0,1)*  part.Thus we want derivations that proceed as follows:

S =>* AB =>* ω A ω^R =>* ω # (0,1)* ω^R (0,1)*

Starting with grammer for (0,1):

C → 0 | 1 Generates (0,1)

generate the language (0,1)*:

B → CB | ε Generates (0,1)*

C → 0 | 1 Generates (0,1)

to generate the language ω # (0,1)* ω^R

as we can see A → ω # B ω^R [ since B Generates (0,1)* ]

so taking A → #B, gives A → ω A ω^R |  #B

for example, take languages - 1 #B 1, 01 #B 10, 101 #B 101.... 000101 #B 101000 (here 000101^R= 101000), etc

As we can see here the production A → 0A0 | 1A1 | #B will produce languages given in above example. Since the recursion with non-terminal A ends only when the transition A → #B, A must generate a string whose beginning and end are mirror images. Hence the non-terminal A generates all strings of the form ω # (0,1)* ω^R

Finally we generate the concatenation of the two languages by adding the production S → AB

The final grammar has start symbol S, auxilliary variables A, B, C and  productions:

S → AB   Generates ω # (0,1)* ω^R (0,1)*
A → 0A0 | 1A1 | #B Generates ω # (0,1)* ω^R
B → CB | ε Generates (0,1)*
C → 0 | 1 Generates (0,1)

Note that this also covers the case where ω = ε. Since A is followed by B in the transition for the top-level nonterminal S, the grammar generates all strings of the form ω # (0,1)* ω^R (0,1)*

Hence, we have build the CGF's for Grammer L = { ω#x | ω^R is a substring of x and x, w ∈ {0,1}* } where ω^R is ω reversed, it proves that the following grammer is Context-free....