Computer Science Engineering (CSE)  >  Theory of Computation  >  Normal Forms of Context Free Grammar Download as PDF

Normal Forms of Context Free Grammar


Test Description

10 Questions MCQ Test Theory of Computation | Normal Forms of Context Free Grammar

Normal Forms of Context Free Grammar for Computer Science Engineering (CSE) 2022 is part of Theory of Computation preparation. The Normal Forms of Context Free Grammar questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Normal Forms of Context Free Grammar MCQs are made for Computer Science Engineering (CSE) 2022 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Normal Forms of Context Free Grammar below.
Solutions of Normal Forms of Context Free Grammar questions in English are available as part of our Theory of Computation for Computer Science Engineering (CSE) & Normal Forms of Context Free Grammar solutions in Hindi for Theory of Computation course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Normal Forms of Context Free Grammar | 10 questions in 30 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study Theory of Computation for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
1 Crore+ students have signed up on EduRev. Have you?
Normal Forms of Context Free Grammar - Question 1

One of the uses of CNF is to turn parse tree into:

Detailed Solution for Normal Forms of Context Free Grammar - Question 1

CNF (Chomsky’s normal form). A grammar is in the form of CNF is as follows:
S → AB
S → a
Where A, B are non-terminals and a is the terminal.
All productions should be of length 2.

  • In this, first eliminate useless symbols for CNF. Eliminate the null productions and unit productions.
  • In CFL it is possible to find atmost two short substrings that we can pump i times for any integer i.
  • Pumping Lemma for CFL is used to examine the size of parse trees. One of the uses of CNF is to turn the parse into binary trees. 
Normal Forms of Context Free Grammar - Question 2

Which of the following grammar is in Greibach Normal Form?
A. S → AB, A → a, B → b
B. S → aA | A → ϵ
C. S → Aa, A → a

Detailed Solution for Normal Forms of Context Free Grammar - Question 2

A context grammar is said to be in Greibech Normal Form if all the productions have the form
S → xA
where x ϵ T and x ϵ V*
T is terminal and V is variable (non-terminal)

  • Option A: Not in GNF. Since production S → AB is not in GNF
  • Option B: Not in GNF. Since production A → ϵ is not in GNF
  • Option C: Not in GNF. Since production S → Aa is not in GNF
Normal Forms of Context Free Grammar - Question 3

What is the minimum number of productions present in the below given context free grammar to make it Chomsky Normal Form?
S → XYx
X → xxy
Y → Xz

Detailed Solution for Normal Forms of Context Free Grammar - Question 3

Concepts:
A context-free grammar is in Chomsky Normal Form if all productions are of the form
A → BC or A → a
{A, B, C} ϵ V and a ϵ T
V is variable(non-terminal) and a is terminal

Calculation:
S → XA
A → YB
B → x
X → BC
C → BD
D → y
Y → XE
E → z

Normal Forms of Context Free Grammar - Question 4

A CFG (Context Free Grammar) is said to be in Chomsky Normal Form (CNF), if all the productions are of the form A → BC or A → a. Let G be a CFG in CNF. To derive a string of terminals of length x, the number of products to be used is

Detailed Solution for Normal Forms of Context Free Grammar - Question 4

Concept:
A context-free grammar is in Chomsky Normal Form if all productions are of the form
A → BC or A → a
{A, B, C} ϵ V and a ϵ T
V is variable(non-terminal) and a is terminal

Formula:
n = 2x - 1
number of productions required to generates string of length x.
where x is the length of the string

Example:
Production:
S → XY
X → a
Y → b
Derive the string ab
S → XY
S → aY
S → ab
Number of productions needed = 3
Verification
2x - 1 = 2(2) - 1 = 3

Normal Forms of Context Free Grammar - Question 5

Let G = (V, T, S, P) be any context-free grammar without any λ-productions or unit productions. Let K be the maximum number of symbols on the right of any production in P. The maximum number of production rules for any equivalent grammar in Chomsky normal form is given by:

Where |⋅| denotes the cardinality of the set.

Detailed Solution for Normal Forms of Context Free Grammar - Question 5

Concept:
Context free grammar : A grammar G = (V, T ,S, P) is said to be context- free if all productions in P have the form A -> x where A ϵ V and x ϵ (V U T)*.

Explanation:
If context free grammar G = (V, T, S, P) is without λ-productions or unit productions.
K = maximum number of symbols on right side of production.
The maximum number of production rules for equivalent grammar in CNF:
(K - 1)|P| + |T|
A context free grammar is in CNF (Chomsky normal form) if it satisfies these conditions:
1. Should not contains null or unit productions.
2. A non-terminal symbol generating two non-terminals. For example, S -> AB
3. A non- terminal generating a terminal. Example: S -> a

Normal Forms of Context Free Grammar - Question 6

To obtain a string of n Terminals from a given Chomsky normal form grammar, the number of productions to be used is:

Detailed Solution for Normal Forms of Context Free Grammar - Question 6

Concept:
Chomsky normal form
S → AB
A → a
B → b
Length of string = n

Length of the derivate of string n in context free grammar:
2|n| – 1

Example:
If we need to generate ab (string of length 2)
S → AB
S → aB
S → ab
Number of steps = 2 × 2 – 1 = 3

*Answer can only contain numeric values
Normal Forms of Context Free Grammar - Question 7

What is the minimum number of productions needed to add to the below given context free grammar to make it Greibech Normal Form?
S → aSb | ab | bb


Detailed Solution for Normal Forms of Context Free Grammar - Question 7

Concepts:
A context grammar is said to be in Greibech Normal Form if all the productions have the form
S → xA
where x ϵ T and A ϵ V*

Calculation:
S → aSB | aB | bB
B → b
The minimum number of productions added is 1.

Normal Forms of Context Free Grammar - Question 8

If L(G) is accepted by pushdown automaton and x is a string of length 21 in L(G), how long is a derivative of x in G, if G is Chomsky normal form?

Detailed Solution for Normal Forms of Context Free Grammar - Question 8

Chomsky normal form
S → AB
A → a
B → b
Length of string = |x|

Length of the derivate of string x in context free grammar:
2|x| – 1 = 2 × 21 - 1 = 41

Note:
Question say steps needed to generated string of 10 length
e.g. if we need to generate ab (string of length 2)
S → AB
S → aB
S → ab
Number of steps = 2× 2 – 1 = 3

*Answer can only contain numeric values
Normal Forms of Context Free Grammar - Question 9

If a Context Free Grammar G is in Chomsky Normal Form, to derive a string of length 101 number of productions needed is _____.


Detailed Solution for Normal Forms of Context Free Grammar - Question 9

Concepts:
A context-free grammar is in Chomsky Normal Form if all productions are of the form
A → BC or A → a
{A, B, C} ϵ V and a ϵ T
V is variable(non-terminal) and a is terminal

Data:
x = 101
n → number of productions required to generates string of length x.

Formula:
n = 2x – 1

where x is the length of the string

Calculation:
n = 2(101) – 1
∴ n = 201

*Answer can only contain numeric values
Normal Forms of Context Free Grammar - Question 10

Let G be a Context Free Grammar in Chomsky Normal Form. To derive a string (aaaaaa)n where a is terminal variable and n is 5, the number of products to be used is _____.


Detailed Solution for Normal Forms of Context Free Grammar - Question 10

Concepts:
A context-free grammar is in Chomsky Normal Form if all productions are of the form
A → BC or A → a
{A, B, C} ϵ V and a ϵ T
V is variable(non-terminal) and a is terminal

Data:
Since n = 5
(aaaaaa)5
Length of string = x = 30

Formula:
The number of products used = 2x – 1
where x is the length of the string

Calculation:
number of products = 2x – 1 = 2 × 30 – 1 = 59

18 videos|56 docs|41 tests
Use Code STAYHOME200 and get INR 200 additional OFF
Use Coupon Code
Information about Normal Forms of Context Free Grammar Page
In this test you can find the Exam questions for Normal Forms of Context Free Grammar solved & explained in the simplest way possible. Besides giving Questions and answers for Normal Forms of Context Free Grammar, EduRev gives you an ample number of Online tests for practice