GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
874 views
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
asked in Theory of Computation by Active (1.3k points)  
edited by | 874 views
Ans given is c Need explanation

DIAGRAM

IN THE OPTION 'C' CONSIDER EITHER M>N (OR) N>K

1ST CASE: CONSIDER M>N THEN LANGUAGE IS L={a^mb^n/m>} IGNORE THE 'C' TERMS THEN IT IS DPDA

2ND CASE:CONSIDER N<K THEN LANGUAGE IS L={b^nc^k/m>} IGNORE THE 'A' TERMS THEN IT IS DPDA

^^ it look like something in my hand writing

yes ,for better understanding i just paste the image

what does this mean:

         q2      (b,z0,z0)   $\rightarrow$  q4 mean in the above diagram ?

@amsar that was solution for something else

$L =\{a^mb^nc^k \;|\;m\neq n\}$

So $q_2$ to $q_4$ was for $m<n$

2 Answers

+4 votes
Best answer
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.
answered by Veteran (294k points)  
selected by
For B). It is " if (m=n) then (n!=k) "

.i.e, if P then Q

P -> Q <=> (P)' $\cup$ Q, rt ?
yes..
But, sir u have written " m≠n or n==k " .

Won't it be m≠n or n$\neq$k
Thanks, corrected..
Hence both option b , c is correct , Beautiful explanation Sir, Thank you!
+5 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 

answered by Veteran (15.1k points)  

@Umang , can u check this line - 

    we can do it using one stack since we have already popped a using b so we cant match the c to k

enlightenedits can't typing mistake.

We having nothing left in stack after ensuring  m=n,  so we can't ensure n! =k (or n=k)  later.


Top Users Sep 2017
  1. Habibkhan

    6836 Points

  2. Arjun

    2310 Points

  3. Warrior

    2306 Points

  4. rishu_darkshadow

    2076 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. Bikram

    1744 Points

  9. SiddharthMahapatra

    1718 Points

  10. makhdoom ghaya

    1690 Points


26,038 questions
33,649 answers
79,695 comments
31,069 users