retagged by
411 views
0 votes
0 votes

Which of the following statements are NOT true?

  1. Given two regular grammars $G1$ and $G2$, it is undecidable whether $L (G1) = L (G2)$.
  2. Given two arbitrary context-free grammars  $G1$ and $G2$, it is undecidable whether $L (G1) = L(G2)$.
  3. All recursive enumerable languages would be recursive, if halting problem is decidable.
  4. For any CFG, it is undecidable whether or not a particular non-terminal "X"  in G is reachable.
  1. I,IV and II
  2. II and IV
  3. I and IV
  4. I,II and III
retagged by

1 Answer

Best answer
2 votes
2 votes

it's screenshot of peter linz so statement 3 is true

selected by
Answer:

Related questions

1 votes
1 votes
0 answers
1
4 votes
4 votes
0 answers
3
Bikram asked Aug 12, 2017
607 views
The number of possible finite automata with two states $a0$ and $a1$ (where $a0$ is always the initial state over the alphabet $\{p, q\}$) which accepts empty language is...
0 votes
0 votes
1 answer
4
Bikram asked Aug 12, 2017
260 views
What is the regular expression corresponding to the above DFA?$(01 + (00)^*1)^*$$0^*10^*$$(10 + 0(00)^* (1 + 01) )^*$$0(00)^*10^*$