recategorized
3,375 views
1 votes
1 votes

Assume the statements $S_1$ and $S_2$ given as:

$S_1$: Given a context free grammar G, there exists an algorithm for determining whether L(G) is infinite.

$S_2$: There exists an algorithm to determine whether two context free grammars generate the same language.

Which one of the following is true?

  1. $S_1$ is correct and $S_2$ is not correct
  2. Both $S_1$ and $S_2$ are correct
  3. Both $S_1$ and $S_2$ are not correct
  4. $S_1$ is not correct and $S_2$ is correct
recategorized

1 Answer

Best answer
5 votes
5 votes

Answer A: S1 is correct but S2 is wrong!

  1. For a Context free language: Membership, Emptiness, Finiteness are decidable. ie we can make an algorithm to check whether a given CGLis infinite or not.
  2. But we cannot design an algorithm to check equivalence of two CFLS.

Very important.

Following are decidable for various types of languages

  • Regular language: {Membership, Emptiness, Finiteness, Equivalence, Everything (Σ*), Ambiguity, Regularity, Disjointedness}
  • Context free language: {Membership, Emptiness, Finiteness}
  • Context sensitive : {Membership }
  • Recursive: {Membership }
  • Recursive Enumerable : None.

Hope now you can easily solve this type of questions

selected by
Answer:

Related questions

1 votes
1 votes
1 answer
1
go_editor asked Jul 20, 2016
1,503 views
LL grammar for the language $L = \{a^n b^m c^{n+m} \mid m \geq 0, n \geq 0\}$ is$ S \rightarrow aSc \mid S_1 ; S_1 \rightarrow bS_1c \mid \lambda$$ S \rightarrow aSc \mid...
4 votes
4 votes
3 answers
3
go_editor asked Jul 20, 2016
1,225 views
Regular expression for the language $L=w \in \{0,1\}* \mid w$ has no pair of consecutive zeros $\}$ is$(1+010)*$$(01+10)*$$(1+010)*(0+ \lambda)$$(1+01)* (0+\lambda)$
1 votes
1 votes
2 answers
4
go_editor asked Jul 20, 2016
3,546 views
The number of states in a minimal deterministic finite automaton corresponding to the language $L=\{ a^n \mid n \geq 4 \}$ is3456