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

Awesome q2a theme

0 votes

This language is CFL or not –

$\Sigma = \{ a,b \} $ and

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

please give the reason also

$\Sigma = \{ a,b \} $ and

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

please give the reason also

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

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.

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??

+1 vote

Best answer

0 votes

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

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 votes

http://ccs.neu.edu/home/viola/classes/slides/slides-context-free.pdf gives the grammar for it!

9,020 questions

3,138 answers

14,456 comments

95,829 users