edited by
5,270 views
5 votes
5 votes
Which of the following language is $CFL$?

a. $\{a^mb^nc^n\;|\;m!=n\}$

b. $\{a^mb^nc^k\;|\;if\,(m=n)\,then\,(n!=k)\}$

c. $\{a^mb^nc^k\;|\;m>n\;or\;n<k\}$

d. None of these
edited by

2 Answers

Best answer
14 votes
14 votes
a. $\{a^mb^nc^n \mid m!=n\}$

We need to ensure #a $\neq$ #b, but also #b = #c. Both of these conditions are not restricted to any finite value and hence cannot be checked simultaneously using a PDA. So, $L$ is a CSL.

b. $\{a^mb^nc^k \mid \text{if }(m=n)\text{ then }(n\neq k)\}$

We have 2 condition to be checked here - either $m\neq n$ or $n \neq k$ in either case we accept a string and reject otherwise. Both of these checks are again not restricted to any finite values but we need not check them together as the conditions are separated by "OR". Hence this can be done using an NPDA making this language a CFL but not DCFL.
c. $\{a^mb^nc^k\mid m>n\text{ or }n<k\}$

Similar to 'b', is CFL but not DCFL.
selected by
4 votes
4 votes

for cfl if there is one comparison at one time then its a CFL.

a) $a^mb^nc^n$ | m!=n 

here two comparison first b= c and a !=b & c so not a cfl 

b) $a^mb^nc^k$  | if(m=n) then n!=k
here first we have to compare a=b if it is yes then n!=k 
we can't do it using one stack since we have already popped a using b to match m=n so we cant match the n to k.

c) $a^mb^nc^k$  | m>n or n<k  
here at one time only one compare if m>n then we dont have to check for n<K or vice versa and it can be done by NPDA.

so option c 

Related questions

1 votes
1 votes
1 answer
2
0 votes
0 votes
1 answer
3
- asked Jan 17, 2016
437 views
(a+b)^* a^n b^n n>=1
0 votes
0 votes
1 answer
4
sumit kumar asked Jun 22, 2015
7,931 views
my question is whether we have a shortcut an idea which can help us in recognizing any language to be regular or not,in GATE .and also what is the best way to get it prop...