The Gateway to Computer Science Excellence
0 votes
767 views

Match the following :

LIST-I LIST-II
a. Chomsky Normal form  i. $S \rightarrow b S S | a S | c$ 
b. Greibach Normal form ii. $S \rightarrow a S b | ab$
c. S-grammar iii. $S \rightarrow AS | a A \rightarrow SA | b$
d. LL grammar iv. $S \rightarrow a B S B B \rightarrow b$ 
  1. a-iv; b-iii; c-i; d-ii
  2. a-iv; b-iii; c-ii; d-i
  3. a-iii; b-iv; c-i; d-ii
  4. a-iii; b-iv; c-ii; d-i
in Theory of Computation by Boss (30.1k points)
edited by | 767 views

1 Answer

+1 vote

a) In Chomsky normal form  all of its production rules should be of the form:

ABC,   or
Aa,   or
S → ε,
iii satisfies this
 
b) In  Greibach normal form, if all production rules are of the form:
A → aA1A2...An or
A a
iv satisfies this
c) A context free grammar is an s-grammar if and only if every production's right hand side begins with a terminal symbol and this terminal is different for any two productions with the same left-hand side.
i satisfies this
 
d) In LL grammar, two production rules can begin  with same terminal symbols if they have same select sets.
ii satisfies this
 
ANSWER :C
by Boss (32.5k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,648 questions
56,430 answers
195,211 comments
99,927 users