The Gateway to Computer Science Excellence
–1 vote
98 views

Consider the given below languages L1 and L2.

L1= {pnqmrmsn | m,n ≥ 0}

L2= {pnqnrmsm | m,n ≥ 0}

Select the correct statement about, L such that

L= (L1 U L2 ) – (L1 ꓵ L2 )

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.

in Theory of Computation by Active (3.4k points) | 98 views
0
L1 is DCFL

L2 is DCFL

L1 U L2 is not DCFL as not closed under union hence CFL move upwards the Chomsky hierarchy.

L1 $\bigcap_{}^{}$ L2 is not DCFL nor CFL hence CSL.CSL is closed under set difference so shouldn't the answer not be CSL?

Please Correct me if I am wrong
0

@sripo

L1 = ab and L2 = anbn n>0 , both are DCFL, what will be there union? anbn n>0 which is again DCFL. This proves that union of 2 DCFL's can be a DCFL. I agree DCFL's are not closed under union, this implies that that their result may or may not be a DCFL. I don't think for a given language we can directly say as the union is not closed and hence the language is not closed. We need some analysis.

Now L1 intersection L2 gives all strings with equal no. of p,q,r,s. calculating union is pretty complicated though, according to union resultant language should accept equal no. of ps and qr or equal no. of pq and rs. So lets say I first started with equal no. of p's and s's and found out they are not equal, now I have to check again if there are equal no.of p's and q's. This can't be done by DCFL as stack will be used in first case(counting of p is gone) but I think it is quite possible by NPDA. Hence I can say that it is not a DCFL but a NCFL is possible, hence we can say DCFL is not possible but language is cfl.

If they would not have subtracted L1 intersection L2 then we could have had problem as we can't design a pda with equal no. of pqrs.

+1
Please add "which" test series
0
L1 is not ab,the grammar is

S->pSs|pAs|∈

A->qAr|qr|∈
0
@Arjun Sir

 Please help with the answer
0
Sripo I was giving an example.
0

@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?

 

0
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.
0
but I still don't know how to conclude its a csl, just by looking at options one can identify its a csl.

1 Answer

0 votes
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.
by Active (2.4k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,508 answers
195,519 comments
100,952 users