edited by
8,047 views
29 votes
29 votes

Which of the following statements is false?

  1. The Halting Problem of Turing machines is undecidable

  2. Determining whether a context-free grammar is ambiguous is undecidable

  3. Given two arbitrary context-free grammars $G_1$ and $G_2$ it is undecidable whether $L(G_1) = L(G_2)$

  4. Given two regular grammars $G_1$ and $G_2$ it is undecidable whether $L(G_1) = L(G_2)$

edited by

2 Answers

Best answer
33 votes
33 votes

Answer is D.

Equivalence of Regular languages is decidable.

  1. Membership,
  2. Emptiness,
  3. Finiteness,
  4. Equivalence,
  5. Ambiguity,
  6. Regularity,
  7. Everything,
  8. Disjointedness...

All are decidable for Regular languages.

First $3$ for CFL.

Only $1$st for CSL and REC.

None for RE.

edited by
3 votes
3 votes

A) halting problem of turing machine are undecidable.

B) Ambiguty problem of CFG  are undecidable

C) equvalance problem of CFG is undecidable

d)  equvalance problem of regular grammar is decidable

so option d is correct option

Answer:

Related questions

30 votes
30 votes
6 answers
1
Kathleen asked Oct 9, 2014
10,083 views
Which two of the following four regular expressions are equivalent? ($\varepsilon$ is the empty string).$(00)^ * (\varepsilon +0)$$(00)^*$$0^*$$0(00)^*$(i) and (ii)(ii) a...
23 votes
23 votes
6 answers
2
Kathleen asked Oct 9, 2014
6,217 views
If $L_1$ and $L_2$ are context free languages and $R$ a regular set, one of the languages below is not necessarily a context free language. Which one?$L_1.L_2$$L_1 \cap L...
23 votes
23 votes
1 answer
3
Kathleen asked Oct 9, 2014
5,625 views
A critical section is a program segmentwhich should run in a certain amount of timewhich avoids deadlockswhere shared resources are accessedwhich must be enclosed by a pa...
35 votes
35 votes
6 answers
4
Kathleen asked Oct 9, 2014
12,518 views
Relative mode of addressing is most relevant to writing:Co – routinesPosition – independent codeShareable codeInterrupt Handlers