Awesome q2a theme
0 votes
200 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 \}$
please give the reason also
in Theory of Computation by (37 points)
edited by | 200 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

3 Answers

+1 vote
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

Ref:https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011/lecture-notes/MIT6_045JS11_lec05.pdf

by (679 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.

https://www.youtube.com/watch?v=KnJnM4bL2ok

0
ok, checking. But for this language, my explaination has no fault , I think
0
No ...you are proving the language to be non-regular.
0

@Satbir chk this question too

0 votes
by (73 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Feb 2020
  1. shashin

    363 Points

  2. Shaik Masthan

    79 Points

  3. SuvasishDutta

    39 Points

  4. srestha

    33 Points

  5. Mk Utkarsh

    32 Points

  6. neeraj_bhatt

    31 Points

  7. !KARAN

    30 Points

  8. Debapaul

    23 Points

  9. Pratyush Priyam Kuan

    18 Points

  10. kalra05

    18 Points

Monthly Top User and those within 60% of his/her points will get a share of monthly revenue of GO subject to a minimum payout of Rs. 500. Current monthly budget for Top Users is Rs. 75.
3,314 questions
1,581 answers
10,271 comments
89,904 users