Register

Test by Bikram | Theory of Computation | Test 1 | Question: 3

• edited by
367 views
3 votes
3 votes

Which of the following grammars violate the Chomsky Normal Form?

  1. $S \rightarrow AB$, $A \rightarrow a , B \rightarrow \epsilon \mid b$
  2. $S \rightarrow AcB, A \rightarrow a, B \rightarrow b$
  3. $S \rightarrow AB, \ A \rightarrow a, \ B \rightarrow b$
  1. All of the above
  2. (i) only
  3. (i) and (ii)  only
  4. (ii) and (iii) only
• edited by
User Avatar

1 Answer

Best answer
5 votes
5 votes

CNF: V->VV         V->t    where V is single variable and t is single terminal
1) CNF doesn't contain epsilon
2) S--> AcB  not in the form of V->VV
3) CNF

• selected by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

6 votes
6 votes
2 answers
1
Bikram asked Nov 26, 2016
1,236 views
Test by Bikram | Theory of Computation | Test 1 | Question: 30
Given a regular grammar $G_1$ and a context free grammar $G_2$, the problem of deciding if $L(G_1)$ is a proper subset of $L(G_2)$ is: Decidable Undecidable but semi-decidable Not even semi-decidable Indeterminable
Given a regular grammar $G_1$ and a context free grammar $G_2$, the problem of deciding if $L(G_1)$ is a proper subset of $L(G_2)$ is:DecidableUndecidable but semi-decida...
User Avatar
0 votes
0 votes
1 answer
2
Bikram asked Nov 26, 2016
317 views
Test by Bikram | Theory of Computation | Test 1 | Question: 29
$G1$ and $G2$ are regular grammars and the language generated by any grammar $G$ is represented by $L(G)$. In this case, $L(G1) \cap L(G2) = \phi$ is a/an: Decidable problem Undecidable problem Cannot ascertain None
$G1$ and $G2$ are regular grammars and the language generated by any grammar $G$ is represented by $L(G)$. In this case, $L(G1) \cap L(G2) = \phi$ is a/an:Decidable prob...
User Avatar
0 votes
0 votes
1 answer
3
Bikram asked Nov 26, 2016
226 views
Test by Bikram | Theory of Computation | Test 1 | Question: 28
Recursive Enumerable Languages are NOT closed under : Union Intersection Complement Homomorphism
Recursive Enumerable Languages are NOT closed under :UnionIntersectionComplementHomomorphism
User Avatar
0 votes
0 votes
1 answer
4
Bikram asked Nov 26, 2016
223 views
Test by Bikram | Theory of Computation | Test 1 | Question: 27
If $S$ and $T$ are languages over $\Sigma =\{a,b\}$ represented by the regular expressions $(a+b^*)^*$ and $(a+b)^*$ respectively, then which of the following options is CORRECT? $S \subset T$ $T \subset S$ $S = T$ $S \cap T = \emptyset$
If $S$ and $T$ are languages over $\Sigma =\{a,b\}$ represented by the regular expressions $(a+b^*)^*$ and $(a+b)^*$ respectively, then which of the following options is ...
User Avatar
Link Copied!