The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged cnf
0
votes
0
answers
1
Ullman (Compiler Design) Edition 2 Exercise 4.4 Question 8 (Page No. 232)
A grammar is said to be in Chomsky Normal Form (CNF) if every production is either of the form $A\rightarrow BC$ or of the form $A\rightarrow a$, where $A, B$, and $C$ are nonterminals, and a is a ... CNF grammar for the same language (with the possible exception of the empty string  no CNF grammar can generate $\epsilon$).
asked
Aug 20
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
51k
points)

2
views
ullman
compilerdesign
cnf
grammar
descriptive
0
votes
0
answers
2
Ullman (Compiler Design) Edition 2 Exercise 4.4 Question 5 (Page No. 231  232)
The grammar $S\rightarrow a\:S\:a \mid \:a\: a$ generates all evenlength strings of $a's$. We can devise a recursivedescent parser with backtrack for this grammar. If we choose to expand by ... the construction of a "Chomsky Normal Form" grammar from arbitrary grammars, as defined in Question $4.4.8$.
asked
Aug 20
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
51k
points)

3
views
ullman
compilerdesign
cnf
recursivedescentparser
descriptive
0
votes
1
answer
3
Michael Sipser Edition 3 Exercise 2 Question 35 (Page No. 157)
Let $G$ be a $CFG$ in Chomsky normal form that contains $b$ variables$.$ Show that if $G$ generates some string with a derivation having at least $2^{b}$ steps$, L(G)$ is infinite$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
51k
points)

29
views
michaelsipser
theoryofcomputation
contextfreelanguages
cnf
proof
+1
vote
1
answer
4
Michael Sipser Edition 3 Exercise 2 Question 26 (Page No. 157)
Show that if $G$ is a $CFG$ in Chomsky normal form$,$ then for any string $w\in L(G)$ of length $n\geq 1,$ exactly $2n − 1$ steps are required for any derivation of $w.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
51k
points)

25
views
michaelsipser
theoryofcomputation
contextfreegrammars
cnf
proof
0
votes
1
answer
5
Michael Sipser Edition 3 Exercise 2 Question 14 (Page No. 156)
Convert the following $\text{CFG}$ into an equivalent $\text{CFG}$ in Chomsky normal form,using the procedure given in $\text{Theorem 2.9.}$ $A\rightarrow BAB \mid B \mid \epsilon$ $B\rightarrow 00 \mid \epsilon$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
51k
points)

22
views
michaelsipser
theoryofcomputation
contextfreegrammars
cnf
+2
votes
1
answer
6
CONVERT CFG TO GNF
S→ AB A→ BSb B→ SAa INTO GNF
asked
Dec 14, 2018
in
Theory of Computation
by
Menon Karthik
(
41
points)

543
views
gnf
cnf
theoryofcomputation
contextfreelanguage
0
votes
1
answer
7
UGCNETJuly2018II35
To obtain a string of n Terminals from a given Chomsky normal from grammar, the number of productions to be used is $2n1$ $2n$ $n+1$ $n^2$
asked
Jul 13, 2018
in
Theory of Computation
by
Pooja Khatri
Boss
(
10.8k
points)

285
views
ugcnetjuly2018ii
theoryofcomputation
cnf
0
votes
0
answers
8
what is cnf for following grammer ?
Eliminate ε productions, unit productions, useless symbols and then rewrite the resulting grammar in the Chomsky Normal Form (in that order) for the following two input grammars: S > 0E0  1FF  ε E > G F > S  E G > S  ε
asked
Apr 10, 2018
in
Theory of Computation
by
hem chandra joshi
Active
(
4.1k
points)

152
views
theoryofcomputation
cnf
+2
votes
1
answer
9
CFG to GNF
Convert the given CFG to GNF. $S \rightarrow MN$ $M\rightarrow aMb\epsilon $ $N\rightarrow aNb\epsilon $
asked
Mar 25, 2018
in
Theory of Computation
by
Mk Utkarsh
Boss
(
35.2k
points)

421
views
theoryofcomputation
contextfreelanguage
cnf
gnf
+1
vote
1
answer
10
Explain This
Every grammar in Chomsky normal form is contextfree, and conversely, every contextfree grammar can be transformed into an equivalent one[note 1] which is in Chomsky normal form and has a size no larger than the square of the original grammar's size. Source https://en.m.wikipedia.org/wiki/Chomsky_normal_form
asked
Jan 22, 2018
in
Theory of Computation
by
Anshul Shankar
Active
(
1k
points)

108
views
theoryofcomputation
cnf
+1
vote
1
answer
11
Chomskey Normal Form
State true/false In CNF , S> espilon and Start symbol can appear on RHS side of production.
asked
Jan 1, 2018
in
Theory of Computation
by
Anjan
Active
(
1.3k
points)

183
views
theoryofcomputation
cnf
0
votes
0
answers
12
Chomsky Normal Form
asked
Dec 10, 2017
in
Theory of Computation
by
Sanjay Sharma
Boss
(
48.5k
points)

122
views
theoryofcomputation
cfg
cnf
0
votes
1
answer
13
UllmanChomsky Normal Form
If the start symbol derives epsilon.Can we eliminate all epsilons while converting to Chomsky Normal Form?Following question from ullman the answer given they have removed the epsilon.But I think if the start symbol derives epsilon,more accurately if L(G) contains epsilon we cannot remove it. S>ASBepsilon A>aASa B>SbSAbb
asked
Nov 25, 2017
in
Theory of Computation
by
Surajit
Active
(
3.7k
points)

147
views
theoryofcomputation
cfg
cnf
+1
vote
1
answer
14
How many variables does the following grammar have when converted to CNF?
E > E+T E > T T > (E) T > i
asked
Nov 18, 2017
in
Theory of Computation
by
gari
Active
(
3.5k
points)

172
views
cnf
theoryofcomputation
0
votes
0
answers
15
Automata: CFG to CNF
As the null string belongs to the language generated by the grammar, answer of the following questions should be "none of these"?
asked
Oct 29, 2017
in
Theory of Computation
by
Manu Thakur
Boss
(
43k
points)

332
views
theoryofcomputation
cnf
0
votes
0
answers
16
Automata: Conversion from CFG to CNF
Convert the following context free grammar into Chomsky Normal Form: $S \rightarrow ASA  aB$ $A \rightarrow B  S$ $B \rightarrow b  \epsilon$ Does the appearance of starting symbol S at RHS impacts the conversion from CFG to CNF?
asked
Oct 14, 2017
in
Theory of Computation
by
Manu Thakur
Boss
(
43k
points)

1.1k
views
theoryofcomputation
contextfreelanguage
cnf
simplification
+1
vote
0
answers
17
CNF and GNF
Given answer is (a) but L>AB i think it is wrong because A and B produce something else Previously, so instead of L>AB there would have given like L>MN M>c1 and N>S then it was correct . if I am wrong please correct me.
asked
Aug 6, 2017
in
Compiler Design
by
learner_geek
Active
(
3.2k
points)

476
views
theoryofcomputation
contextfreelanguage
discretemathematics
derivationtree
cnf
+1
vote
0
answers
18
CNF and GNF
Is it mandatory in GNF that first element in production must be terminal(I am considering there is no Left recursion) Is it mandatory in CNF that in production only two nonterminal or terminal should be there Can we not take in one production as two nonterminal and one terminal OR one terminal and two nonterminal
asked
Aug 5, 2017
in
Theory of Computation
by
learner_geek
Active
(
3.2k
points)

1.2k
views
theoryofcomputation
derivationtree
contextfreelanguage
cnf
+2
votes
1
answer
19
Raghunath Tiwari(NPTEL NOC Chomsky Normal Form)
S>ASB A>aASA  a  ϵ B>SbS  A  bb Convert this grammar into Chomsky Normal Form
asked
Jul 3, 2017
in
Theory of Computation
by
Veeplob Singh
(
47
points)

219
views
theoryofcomputation
cfg
cnf
grammar
0
votes
1
answer
20
[TOC] CNF Tree Depth
1. Assume that we have CNF tree of depth of h(Assume root at height 0).What is the maximum yeild possible in terms of h? 2. Assume that we have a string of length n,what is the min and max height of parse tree possible in CNF. Please explain
asked
Jan 12, 2017
in
Theory of Computation
by
rahul sharma 5
Boss
(
24.9k
points)

187
views
theoryofcomputation
contextfreelanguage
cnf
derivationtree
0
votes
1
answer
21
TOC CFG to CNF convertion
asked
Dec 10, 2016
in
Theory of Computation
by
KISHALAY DAS
Active
(
4.9k
points)

194
views
theoryofcomputation
contextfreelanguage
cnf
+1
vote
0
answers
22
#sipser book
Can ambiguous context free grammar be converted into CNF form..?
asked
Sep 14, 2016
in
Theory of Computation
by
Abhishekcs10
Active
(
1.7k
points)

96
views
cfg
cnf
To see more, click for the
full list of questions
or
popular tags
.
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
Recent Posts
Recruitment to the post of Scientist/Engineer 'SC' (Electronics, Mechanical and Computer Science)
Standard Videos for Calculus
Standard Videos for Linear Algebra
Standard Videos for Graph Theory
Standard Videos for Combinatory
Follow @csegate
Recent questions tagged cnf
Recent Blog Comments
it's depend upon your shift.
Can previously appeared candidates tell what is...
i have confirmed through application form that...
Thanks I will try that
Yes, since one can't enter the CGPA/Marks until...
50,309
questions
55,747
answers
192,248
comments
90,536
users