search
Log In
24 votes
2.9k views

Which one of the following problems is undecidable?

  1. Deciding if a given context-free grammar is ambiguous.
  2. Deciding if a given string is generated by a given context-free grammar.
  3. Deciding if the language generated by a given context-free grammar is empty.
  4. Deciding if the language generated by a given context-free grammar is finite.
in Theory of Computation
retagged by
2.9k views
0

For option, C

"Note that L(G) != φ if and only if G’s start variable can generate a string in T∗, where T is G’s terminal alphabet. We simply determine this property for each variable A in G : can A generate a string in T∗ ?"

For option, D found this 

Note that L(G) is infinite exactly if there is a path in a derivation tree with a repeated variable. The following algorithm identifies the variables that can be repeated in this way; L(G) is infinite exactly if there is at least one such variable

From- https://cs.nyu.edu/courses/fall09/V22.0453-001/chapter-4.pdf 4.4.3 & 4.4.6 Example.

0

option b   membership  

option c   emptiness

option d   finiteness 

all are decidable  for cfl 

3 Answers

25 votes
 
Best answer

(A) is the answer. Proving (A) is undecidable is not so easy. But we can easily prove the other three options given here are decidable.

https://gatecse.in/grammar-decidable-and-undecidable-problems/


edited by
0
@Arjun sir option A is undecidable but option D is saying Is CFG closed under finite(Regular Grammar) is it Decidable, please explaine.
3
If A were decidable, then the PCP problem would have been decidable implying that PCP problem is reducible to finding whether a given context-free grammar is ambiguous. Hence undecidable.
0
PCP -> post correspondence problem  ??
0
yes.
3 votes

Context free grammar is not closed under ambiguity.A set is closed under an operation means when we operate an element of that set with that operator we get an element from that set. Here, context free grammar generates a context free language and set of all context free languages is also a set. But, ambiguity is not an operation and hence we can never say that CFG is closed under ambiguity. Thus, problem mentioned in option (A) is undecidable.

–1 vote
A.

CFG is not closed under ambiguity.
15
A set is closed under an operation means when we operate an element of that set with that operator we get an element from that set.

Here, CFG generates a CFL and set of all CFLs is the set. But ambiguity is not an operation and hence you can never say "closed" here.
0

Sir what's the difference between option c) of this question and "G is a CFG. Is L(G)=ϕ?"(which is undecidable as per Rice's Theorem https://gateoverflow.in/1553/gate2013_41).

0
Both are same and both are decidable.
0
but it's proven undecidable in the link I provided. I think "G is a CFG" means it's for any CFG so property becomes non-trivial but here it says "by a given CFG" so here we can see the specific CFG's productions & decide. @Arjun sir is it the reason?
0
where undecidable is given in link can you tell the name of person who write
0
by "Kai". It's not the best answer but I'm not getting why it's wrong.

"Since the Language is (<G>| G is a CFG and L(G) is empty). We can find one TM which accepts an empty string and one which doesn't. Then by Rice's theorem, this property is non trivial and thus undecidable for Recursively Enumerable languages which involve CFLs."
0

#Pcs See it ... Its a trivial property i think ... We jst need to care abt the terminals to  get the result ...

http://www3.cs.stonybrook.edu/~cse350/slides/decide2.pdf

Answer:

Related questions

22 votes
3 answers
1
2.7k views
Consider the following languages over the alphabet $\sum = \{0, 1, c\}$ $L_1 = \left\{0^n1^n\mid n \geq 0\right\}$ $L_2 = \left\{wcw^r \mid w \in \{0,1\}^*\right\}$ $L_3 = \left\{ww^r \mid w \in \{0,1\}^*\right\}$ Here, ... the reverse of the string $w$. Which of these languages are deterministic Context-free languages? None of the languages Only $L_1$ Only $L_1$ and $L_2$ All the three languages
asked Sep 28, 2014 in Theory of Computation jothee 2.7k views
27 votes
6 answers
2
3.8k views
Let $\oplus$ denote the exclusive OR (XOR) operation. Let '1' and '0' denote the binary constants. Consider the following Boolean expression for $F$ over two variables $P$ and $Q$ ... $F$ is $P+Q$ $\overline{P+Q}$ $P \oplus Q$ $\overline {P \oplus Q}$
asked Sep 28, 2014 in Digital Logic jothee 3.8k views
15 votes
2 answers
3
3.2k views
Let $\delta$ denote the minimum degree of a vertex in a graph. For all planar graphs on $n$ vertices with $\delta \geq 3$, which one of the following is TRUE? In any planar embedding, the number of faces is at least $\frac{n}{2}+2$ In any planar embedding, the number of faces ... is less than $\frac{n}{2}+2$ There is a planar embedding in which the number of faces is at most $\frac {n}{\delta+1}$
asked Sep 28, 2014 in Graph Theory jothee 3.2k views
42 votes
11 answers
4
6.7k views
If $G$ is the forest with $n$ vertices and $k$ connected components, how many edges does $G$ have? $\left\lfloor\frac {n}{k}\right\rfloor$ $\left\lceil \frac{n}{k} \right\rceil$ $n-k$ $n-k+1$
asked Sep 28, 2014 in Graph Theory jothee 6.7k views
...