445 views
This language is CFL or not –

$\Sigma = \{ a,b \}$ and
$L = \{ x \# y\ |\ x,y \in \Sigma^*\ , \#\ is \ a \ constant\ and\ x \neq y \}$

edited | 445 views
0
@Debargha

yes, language has some flaws .

But what the  language want to convey, it will not be $w$#$w$. Indeed it is a non-CFL and non CSL too
0
@Srestha,
I think this will be a CSL because we can construct a LBA that begins with the input string on the tape and checks if corresponding bit positions of x and y match one by one (kind of the same thing that @Mrinmoy suggested except that we use a LBA here). If match occurs for all bit positions, then string doesn’t belong to the language. If there is at least one position for which there is no match, then we accept the string. Therefore, we have an acceptor for the language L which accepts the strings which are part of the language and rejects those which are not.
Also, no problem with arbitrary inputs in case of LBA as the tape will adjust to whatever input it gets.
0

If match occurs for all bit positions, then string doesn’t belong to the language. If there is at least one position for which there is no match, then we accept the string

@Debargha

at the same time u are checking two things

First of all for $L=x$#$y$ where $|x|=|y|$

and another thing if $x!=y$

Now it cannot be done in one stack.So, non-CFL for sure.

(which below I proved by pumping lemma)

Now tell me how do u do it with 2 stacks??

0

Though I think , that will not be CSL, as more than one stack work as TM

https://gateoverflow.in/17815/fsm

0

@srestha

you can split those 2 things into 2 non-deterministic case.

1. first we check whether |x| not equal to |y| if not then accept else goto step 2.
2. now take the other path and check whether x not equal to y or not.

@Debargha This is the actual algo which they gave in solution

+1 vote
by (643 points)
selected by
0
0
0

Pumping lemma can be recognized by $L=uv^{i}z$ ,

where in above diagram $u$ represented by $a_{1}a_{2}.......a_{i}$,

$v$ represents some loop, $a_{i}a_{i+1}.......a_{j}$,

and $w$ represented by $a_{j+1}a_{j+2}.......a_{k}$

where $|uv|\leq p$  and $|v|\geq 1$

Now take  $L= 0^{n}$#$0^{n}$

So, we know, $|uv|\leq p$, So, $|uv|$ atmost $0^{n}$

Now, suppose, $u=0$ and $v=0^{n-1}$

But we know, $v$ contains a loop, which can go infinite number of time.

But according to our language $v$ must be contain length which equates $w$, which is a contradiction.

So, pumping lemma fails. It is a non-CFL

by (1k points)
0

$L=0^n\#0^n$ how did you took this ?

and one more thing pumping lemma for CFL and regular language are different.

Pumping lemma can be recognized by $L=uv^iz$,

for CFL we take $L = uv^iwx^iy$

0

$L = uv^iw$ or$L = uv^iwx^iy$

it depends on, if u took one loop or two loops inside the language. That will not matter much.

Also check the link of MIT.

0

The PDA just have examples to prove non-regular and not non-CFL

it depends on, if u took one loop or two loops inside the language. That will not matter much.

it matters a lot. see any NPTEL Video of pumping lemma for CFL you will understand.