The Gateway to Computer Science Excellence
0 votes

Match the following :

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
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
99,927 users