NIELIT 2017 DEC Scientist B - Section B: 11

Question

Which of the following are undecidable?

$P1$: The language generated by some CFG contains any words of length less than some given number $n$.

$P2$: Let $L1$ be CFL and $L2$ be regular, to determine whether $L1$ and $L2$ have common elements

$P3$: Any given CFG is ambiguous or not.

$P4$: For any given CFG $G$, to determine whether epsilon belongs to $L(G)$

• A. $P2$ only
• B. $P1$ and $P2$ only
• C. $P2$ and $P3$ only
• D. $P3$ only

Comments

take string of length 1 and apply CYK for membership then length 2 and continue

---

$\text{P2 is decidable}$ : As intersection of regular language and CFL is decidable.

---

I think option D) is correct.

Answer 1

answer should be C

P1=by using CFG we can generate a string of given length by using all possible production ..now its just a matter of looking any string  generated has length less than specified...so DECIDABLE...

P2= every regular is CFL and  L1 intersection L2 =phi is undecidable for CFL....(L1 and L2 are cfl )

P3=No algo to check that CFG is ambigus or not..

P4=we can determine episolon is in language or not ....IF START SYMBOL itself contain episolon then we can say it belongs to language...

SO P1 and P4 are DECIDABLE and P2 and P3 are undeciable... 

Comments

Answer is Option D

P1 is decidable as CFL have membership algo decidable so it can be checked easily.
P2 is also decidable because ,

L1 is CFL ,L2 is Regular
and it is well known fact that L1 intersection L2( Regular ) is decidable.

 Pushing L2 up and then saying CFL intersection CFL is phi ,is wrong way.

Alternatively one can always find out whether a string is common by generating strings by both an NPDA(CFL) and DFA(Regular)  ,and find out whether the string is accepted by both or not.
P1 is decidable as CFL has  membership ,and P3 is well known undecidable,

---

$p2\; is \:also \:undecidable \: because \:L1\: is\: CFL\: and \:L2 \:is \:Regular\:,\:by\: pushing\: up \:we \:can\: say\: that \:L1 \:and \:L2 \:both\: are \:CFL \:and\: Equivalence \:of\:Two\: CFL\: is \:undecidable\:,\:Answer\: will\: be \:(C)\:P2 \:and\: P3 \:$

---

L intersection Reg => L

---

@ Anand Maurya

Hey, I know that REG ∩ CFL = CFL. BUT can you please tell how did you use the table you have posted to derive that conclusion? 

Answer 2

asked for common elements, which we get by intersection of both language. And intersection of CFL and REGULAR is CFL. Its DECIDABLE.

Comments

Answer is D as per my knowledge because for P2 intersection of CFL and Regular is regular and that's why it is decidable.