retagged by
2,097 views
1 votes
1 votes

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)$

  1. $P2$ only
  2. $P1$ and $P2$ only
  3. $P2$ and $P3$ only
  4. $P3$ only
retagged by

2 Answers

0 votes
0 votes

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... 

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

Related questions

0 votes
0 votes
6 answers
1
admin asked Mar 30, 2020
2,410 views
According to the given language, which among the following expressions does it correspond to ?Language $L=\{x\in\{0,1\}\mid x\text{ is of length 4 or less}\}$.$(0+1+0+1+0...
1 votes
1 votes
3 answers
3
0 votes
0 votes
4 answers
4