203 views
0 votes
0 votes

Please give the solution with reason

1 Answer

0 votes
0 votes
Not Sure about 2nd but will try to answer for 1st and 3rd.

 

1. L is set of all strings where  p <= q <= r and of the form a^pb^qc^r where p is number of a's , q is number of b's , r is number of c's .

Here I think it is not even a CFL as all the strings belonging to this language cannot be accepted by a PDA.

This can be proven using an example . Since the condition is p<=q<=r then all the strings of type p = q = r will also belong to this Language.

Now can a PDA be constructed to match number of a's , b's and c's ?. It cannot be , because if number of a's and b's are matched then the stack would be empty , so number of c's cannot be matched .

Thus we prove that a string belonging to the Language cannot be accepted by a PDA .  So this is not even a CFL.

3. Here it is given that p = m +n.

That is number of c's = Number of a's + Number of b's .

For this easily a Deterministic PDA can be drawn .

Just push all the a's and b's and be in a state.

As soon as C is seen , change state and start popping from the stack .

If on reading Epsilon , the top of stack is Z0 then go to final state and string is accepted , else rejected .  Thus Language is DCFL.

 

Not sure about 2nd One

Related questions

2 votes
2 votes
2 answers
1
Jithin Jayan asked Nov 15, 2016
355 views
If a Language say 'L' is given to be Non Regular. Then can complement of L(Lc) be Regular?
2 votes
2 votes
1 answer
2
Jithin Jayan asked Oct 15, 2016
323 views
Given two DCFLs (L1 and L2) Is L1 = L2 Decidable or not?