The Gateway to Computer Science Excellence

+3 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

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

+12 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.

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.

+4 votes

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

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,666 questions

56,154 answers

193,757 comments

93,718 users