The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+14 votes

Consider the following languages:

- $\{a^mb^nc^pd^q \mid m+p=n+q, \text{ where } m, n, p, q \geq 0 \}$
- $\{a^mb^nc^pd^q \mid m=n \text{ and }p=q, \text{ where } m, n, p, q \geq 0 \}$
- $\{a^mb^nc^pd^q \mid m=n =p \text{ and } p \neq q, \text{ where } m, n, p, q \geq 0 \}$
- $\{a^mb^nc^pd^q \mid mn =p+q, \text{ where } m, n, p, q \geq 0 \}$

Which of the above languages are context-free?

- I and IV only
- I and II only
- II and III only
- II and IV only

+3

m+p=n+q can we rewritten as (m-n=q-p OR n-m=p-q) this can be easily checked by making a NON DETERMINISTIC PUSH DOWN AUTOMATA hence CFL and we know 2 is DCFL hence CFL :)

0

where is the proof? i dont think what i commented above is wrong u can try constructing a NDPDA for 1 with what the hint i have given :)

0

I've a doubt. for first option let string=$a^3b^4c^2d^1$

i push all 3 a's. then I pop one 'a' for every 'b'. now I'm left with 'b' and stack top is empty. what to do next? how is first option CFL?

i push all 3 a's. then I pop one 'a' for every 'b'. now I'm left with 'b' and stack top is empty. what to do next? how is first option CFL?

+1

follow these transition:

Q(b,z_{0}/bz_{0} ), means if the input symbol is b and top of the stack is z_{0} (or empty) then push b

once you start seeing c then for every input c if b is at the top of the stack pop the b and once the stack is empty start pushing c , and once you start seeing d pop the c .

I hope you got it.

0

@Vegeta Both cases are mutually exclusive, we can have either case 1 or 2 not both, so its deterministic.

0

Initially we push 'a' and pop 'b' for each 'a' in both cases and then we define multiple set of transitions in PDA to cover both cases. We can deterministically know which case is the right one by having information about top of the stack and next input symbol.

If #a >= #b: We push 'a' and then pop b for each 'a',** ultimately we would exhaust all b's and there would still be some a's left in the stack**. From this we know this is case #1, so we will have a sequence of transitions for this case.

If #a < #b: We push 'a' and then pop b for each 'a', **at some point we will see there are still b's left while all a's are removed from stack (empty stack)** then we know this is from case #2. So we will follow a different set of transitions from here.

Note: Both sets of transitions are defined in the diagram.

+22 votes

Best answer

$a)\ \{a^mb^nc^pd^q \mid m+p=n+q, \text{ where } m, n, p, q \geq 0 \}$

Grammar :

$S \longrightarrow aSd\ |\ ABC\ |\in$

$A \longrightarrow aAb\ |\ ab\ |\in $

$B \longrightarrow bBc\ |\ bc\ |\in$

$C \longrightarrow cCd\ |\ cd\ |\in $

Above Grammar is CFG so it will generate CFL.

$b)\ \{a^mb^nc^pd^q \mid m=n \text{ and }p=q, \text{ where } m, n, p, q \geq 0 \}$

Grammar :

$S \longrightarrow AB\ |\in $

$A \longrightarrow aAb\ |\ ab$

$B \longrightarrow cBd\ |\ cd$

Above Grammar is CFG so it will generate CFL.

$c)\ \{a^mb^nc^pd^q \mid m=n =p \text{ and } p \neq q, \text{ where } m, n, p, q \geq 0 \}$

More than one comparison so NOT CFL.

$d)\ \{a^mb^nc^pd^q \mid mn =p+q, \text{ where } m, n, p, q \geq 0 \}$

It is CSL but NOT CFL.

Correct Answer: $B$

Grammar :

$S \longrightarrow aSd\ |\ ABC\ |\in$

$A \longrightarrow aAb\ |\ ab\ |\in $

$B \longrightarrow bBc\ |\ bc\ |\in$

$C \longrightarrow cCd\ |\ cd\ |\in $

Above Grammar is CFG so it will generate CFL.

$b)\ \{a^mb^nc^pd^q \mid m=n \text{ and }p=q, \text{ where } m, n, p, q \geq 0 \}$

Grammar :

$S \longrightarrow AB\ |\in $

$A \longrightarrow aAb\ |\ ab$

$B \longrightarrow cBd\ |\ cd$

Above Grammar is CFG so it will generate CFL.

$c)\ \{a^mb^nc^pd^q \mid m=n =p \text{ and } p \neq q, \text{ where } m, n, p, q \geq 0 \}$

More than one comparison so NOT CFL.

$d)\ \{a^mb^nc^pd^q \mid mn =p+q, \text{ where } m, n, p, q \geq 0 \}$

It is CSL but NOT CFL.

Correct Answer: $B$

+1

for 1 : m + p =n + q

can be written as m + p - n - q = 0 => m - n + p - q =0

push a

for each b pop a ,

now if b's are more than a's push rest of a's

if a's are more than b's , a's will be there on stack.

for c's if a's are on stack push c's ,

for c's if b's are on stack pop b's

for d's if a's or c's are on stack pop 1 a or c for each d.

for d's if b's on stack (you can stop here itself as m - n + p - q will not be zero)

for 4 : mn = p+q

what it means is "for each a push n b's on stack"

suppose if we pushed all a's on stack and now b start arriving ,suppose now first b arrived , at this stage we don't know how many b's will arrive eventually . hence we can't push exact number of b's corresponding to this first b's.

hence this is not CFL

can be written as m + p - n - q = 0 => m - n + p - q =0

push a

for each b pop a ,

now if b's are more than a's push rest of a's

if a's are more than b's , a's will be there on stack.

for c's if a's are on stack push c's ,

for c's if b's are on stack pop b's

for d's if a's or c's are on stack pop 1 a or c for each d.

for d's if b's on stack (you can stop here itself as m - n + p - q will not be zero)

for 4 : mn = p+q

what it means is "for each a push n b's on stack"

suppose if we pushed all a's on stack and now b start arriving ,suppose now first b arrived , at this stage we don't know how many b's will arrive eventually . hence we can't push exact number of b's corresponding to this first b's.

hence this is not CFL

+21 votes

0

push 2 a's.

pop 2 a's for 2 b's ( now stack is empty).

push 2 b's .

pop 2 b's for 2 c's.(now stack empty).

push 2 c's.

pop 2 c's for 2 d's ( stack empty , input empty ->accept)

note: think of (ac) in one team and (bd) in another team.

i am not able to get pda for this L. i'll post it when i'll get it :)

pop 2 a's for 2 b's ( now stack is empty).

push 2 b's .

pop 2 b's for 2 c's.(now stack empty).

push 2 c's.

pop 2 c's for 2 d's ( stack empty , input empty ->accept)

note: think of (ac) in one team and (bd) in another team.

i am not able to get pda for this L. i'll post it when i'll get it :)

+6 votes

B is correct and one of the easiest solution for I is CFL as m+p=n+q can be written as m-n+p=q so we can easily construct PDA for I in following steps:-

1)push X for every a

2)pop X for every b

3)push X for every c

finally 4) pop X for every d and if atlast we get empty stack so yes it is valid language so definitely I is CFL So option B.thanks

1)push X for every a

2)pop X for every b

3)push X for every c

finally 4) pop X for every d and if atlast we get empty stack so yes it is valid language so definitely I is CFL So option B.thanks

+3 votes

II is obviously CFL

for option IV as multiplication symbol is not given there we can consider it as concatenation

lets take example

a^30 b^5 c^200 d^105

now here m=30 n=5 p=200 q=105

mn=p+q is 305=305

now we can design pda as following

1)push 10 'a' for Each input 'a' in stack

2)push all b's in stack

now stack contains 305 a's and b's for above example

3)match all a and b in stack with input c and d

4)if stack is empty and input is null then accept otherwise reject

Hence **OPTION D**

+2 votes

Many might have marked B,but one must be able to rigorously prove it:

Why is 4 false?

Here we must know what m is.Multiplication can only be performed if we know one of its operands.There is no bound on m, and since you cannot count till infinity(**counting requires a distinct state for each increment**) and you cannot have infinite states counting is not possible.This can be done with the help of LBA

Why is 2 true?

We'll decompose the problem into 2 parts as we don't have to be deterministic.

Case 1:

m-n = p-q .Do,simple push and pop for 'a' and 'b' respectively.Now,if 'b' is one the stack terminate . else do the similar operation for 'c' and 'd' .Now compare the leftover 'a' with leftover 'c',this is again trivial.

Case 2: n-m = p-q can be done similarly.

**Answer:b)**

+1 vote

For I to be cfl one more condition need to be satisfied along with m+p=n+q that is m>=n

Reference:

https://www.cs.utexas.edu/~cline/ear/automata/CS341-Fall-2004-Packet/3-SupplementaryMaterials/D-SuppContextFree.pdf

check page no 10 of pdf

for option IV as multiplication symbol is not given there we can consider it as concatenation

lets take example

a^30 b^5 c^200 d^105

now here m=30 n=5 p=200 q=105

mn=p+q is 305=305

now we can design pda as following

1)push 10 'a' for Each input 'a' in stack

2)push all b's in stack

now stack contains 305 a's and b's for above example

3)match all a and b in stack with input c and d

4)if stack is empty and input is null then accept otherwise reject

Reference:

https://www.cs.utexas.edu/~cline/ear/automata/CS341-Fall-2004-Packet/3-SupplementaryMaterials/D-SuppContextFree.pdf

check page no 10 of pdf

for option IV as multiplication symbol is not given there we can consider it as concatenation

lets take example

a^30 b^5 c^200 d^105

now here m=30 n=5 p=200 q=105

mn=p+q is 305=305

now we can design pda as following

1)push 10 'a' for Each input 'a' in stack

2)push all b's in stack

now stack contains 305 a's and b's for above example

3)match all a and b in stack with input c and d

4)if stack is empty and input is null then accept otherwise reject

0 votes

I don't think the options are correct(The numbering is wrong). But I can definitely say that I and II, both are CFL as you easily construct PDAs for them. You can easily count the m's, n's & p's, q's in them and them push/pop accordingly.

III is definitely not a CFL. You cannot construct a PDA for it as you have to ensure that m = n = p, that means counting 3 of them and it is also given that p does not equal q, so q can be anything.

So I hope you can figure out the answer(The options are incorrect I think. So, check out!) :)

III is definitely not a CFL. You cannot construct a PDA for it as you have to ensure that m = n = p, that means counting 3 of them and it is also given that p does not equal q, so q can be anything.

So I hope you can figure out the answer(The options are incorrect I think. So, check out!) :)

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2k
- Databases 4.1k
- CO & Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.4k
- Admissions 596
- Exam Queries 577
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

49,532 questions

54,126 answers

187,326 comments

71,046 users