test series

Question

Consider the given below languages L₁ and L₂.

L1= {pⁿq^mr^msⁿ | m,n ≥ 0}

L2= {pⁿqⁿr^ms^m | m,n ≥ 0}

Select the correct statement about, L such that

L= (L₁ U L₂ ) – (L₁ ꓵ L₂ )

1. 

L is CFL but not DCFL

 

2.

L is regular

 

3. 

L is CSL but not CFL

 

4.

L is DCFL but not regular

 

i know that L is representing the EX-OR of L1 and L2, couldn't visualize as how it will be cfl. please help.

Comments

@Swapnil Naik

how NPDA exist ?

 

in P$^i$ Q$^j$ R$^k$ S$^l$

either ( P = Q and R = S ) and ( P ≠ R )

or  ( P = S and R = Q )  and ( P ≠ R )

accepted.... isn't it is CSL?

 

---

I underestimated one fact that I have still have to check |p|=|q|=|r|=|s|, if p is not equal to q then you check whether p is equal to s, and npda is possible for this considering first satisfies their respective intermediate constrains, but then later I realized it is accepting strings where |p|=|q|=|r|=|s|. So I tried to go in details by taking one language at a time.

$p^{n}q^{m}r^{m}s^{n}$ , and n!= m but I didn't found any way to accept this as I first need to check whether n==m or not, which may or may not empty my stack. If I do so I won't be having considerable amount of p's to check with s. and hence it won't be CFL.

Thank you Shaik for pointing out a mistake.

---

but I still don't know how to conclude its a csl, just by looking at options one can identify its a csl.

Answer 1

Correct me if I am wrong but I am being very specific to the given grammar.I think the answer is CSL,but I don't know if my logic behind it is correct please validate my answer.