Is the following grammar a CFG?

53 Views Asked by At

Language $L$ is defined over symbols $a,b,\#$

$$L=\{x\#y\mid x,y∈\{a,b\}^*, x\ne y, \lvert x\rvert=\lvert y\rvert\}$$

Is the above language context free?

Though both conditions separately are context free, but are they context free together?

Thanks.

Edit:

I just found a solution to the question. The above language is NOT Context Free. The same can be proved using pumping lemma for CFLs. Thanks everyone for the help.

1

There are 1 best solutions below

2
On

Minor nit: The given language definition is not a grammar.

The language IS context-free. Here is one grammar (note: the single-quotes merely mark the terminal symbols, they are not part of the language):

S -> L S L | A

A -> 'a' B 'b' | 'b' B 'a'

B -> L B L | '##'

L -> 'a' | 'b'