Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged conjunctive-normal-form
1
votes
0
answers
1
Self doubt about CFG to CNF conversion.
I am still having some doubts when it comes to Context-Free Grammar to Chomsky Normal Form conversion. Here is what I did for the following CFG: $S \rightarrow bXb \ |\ bS \ |\ \epsilon\ |\ aSdSc$ $X \rightarrow aX \ |\ Xtt$ ... $H \rightarrow b$ $A \rightarrow a$ $D \rightarrow d$ $C \rightarrow c$ Did I do this correctly?
I am still having some doubts when it comes to Context-Free Grammar to Chomsky Normal Form conversion. Here is what I did for the following CFG: $S \rightarrow bXb \ |\ b...
HenryAsks21
371
views
HenryAsks21
asked
May 2, 2022
Theory of Computation
theory-of-computation
conjunctive-normal-form
+
–
0
votes
0
answers
2
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$).
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$ ar...
admin
317
views
admin
asked
Aug 20, 2019
Compiler Design
ullman
compiler-design
conjunctive-normal-form
grammar
descriptive
+
–
0
votes
0
answers
3
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 even-length strings of $a's$. We can devise a recursive-descent 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$.
The grammar $S\rightarrow a\:S\:a \mid \:a\: a$ generates all even-length strings of $a's$. We can devise a recursive-descent parser with backtrack for this grammar. If w...
admin
492
views
admin
asked
Aug 20, 2019
Compiler Design
ullman
compiler-design
conjunctive-normal-form
recursive-descent-parser
descriptive
+
–
0
votes
1
answer
4
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$.$
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...
admin
620
views
admin
asked
May 4, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
conjunctive-normal-form
proof
+
–
1
votes
1
answer
5
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.$
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....
admin
506
views
admin
asked
May 4, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
conjunctive-normal-form
proof
+
–
0
votes
1
answer
6
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$
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 ...
admin
2.0k
views
admin
asked
May 4, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
conjunctive-normal-form
+
–
5
votes
1
answer
7
CONVERT CFG TO GNF
S→ AB A→ BS|b B→ SA|a INTO GNF
S→ ABA→ BS|bB→ SA|a INTO GNF
Menon Karthik
26.7k
views
Menon Karthik
asked
Dec 14, 2018
Theory of Computation
gnf
conjunctive-normal-form
theory-of-computation
context-free-language
+
–
0
votes
1
answer
8
UGC NET CSE | July 2018 | Part 2 | Question: 35
To obtain a string of n Terminals from a given Chomsky normal from grammar, the number of productions to be used is $2n-1$ $2n$ $n+1$ $n^2$
To obtain a string of n Terminals from a given Chomsky normal from grammar, the number of productions to be used is$2n-1$$2n$$n+1$$n^2$
Pooja Khatri
1.3k
views
Pooja Khatri
asked
Jul 13, 2018
Theory of Computation
ugcnetcse-july2018-paper2
theory-of-computation
conjunctive-normal-form
+
–
0
votes
0
answers
9
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 | ε
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 ...
hem chandra joshi
1.3k
views
hem chandra joshi
asked
Apr 10, 2018
Theory of Computation
theory-of-computation
conjunctive-normal-form
+
–
3
votes
1
answer
10
CFG to GNF
Convert the given CFG to GNF. $S \rightarrow MN$ $M\rightarrow aMb|\epsilon $ $N\rightarrow aNb|\epsilon $
Convert the given CFG to GNF.$S \rightarrow MN$$M\rightarrow aMb|\epsilon $$N\rightarrow aNb|\epsilon $
Mk Utkarsh
2.8k
views
Mk Utkarsh
asked
Mar 25, 2018
Theory of Computation
theory-of-computation
context-free-language
conjunctive-normal-form
gnf
+
–
1
votes
1
answer
11
Explain This
Every grammar in Chomsky normal form is context-free, and conversely, every context-free 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
Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar can be transformed into an equivalent one[note 1] which is in Chomsky nor...
Anshul Shankar
856
views
Anshul Shankar
asked
Jan 22, 2018
Theory of Computation
theory-of-computation
conjunctive-normal-form
+
–
1
votes
2
answers
12
Chomskey Normal Form
State true/false In CNF , S-> espilon and Start symbol can appear on RHS side of production.
State true/falseIn CNF , S- espilon and Start symbol can appear on RHS side of production.
Anjan
2.9k
views
Anjan
asked
Jan 1, 2018
Theory of Computation
theory-of-computation
conjunctive-normal-form
+
–
0
votes
0
answers
13
Chomsky Normal Form
Sanjay Sharma
801
views
Sanjay Sharma
asked
Dec 10, 2017
Theory of Computation
theory-of-computation
context-free-grammar
conjunctive-normal-form
+
–
0
votes
1
answer
14
Ullman--Chomsky 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->ASB|epsilon A->aAS|a B->SbS|A|bb
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 remove...
Surajit
1.2k
views
Surajit
asked
Nov 25, 2017
Theory of Computation
theory-of-computation
context-free-grammar
conjunctive-normal-form
+
–
1
votes
1
answer
15
How many variables does the following grammar have when converted to CNF?
E -> E+T E -> T T -> (E) T -> i
E - E+TE - TT - (E)T - i
gari
1.6k
views
gari
asked
Nov 18, 2017
Theory of Computation
conjunctive-normal-form
theory-of-computation
+
–
1
votes
1
answer
16
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"?
As the null string belongs to the language generated by the grammar, answer of the following questions should be "none of these"?
Manu Thakur
6.1k
views
Manu Thakur
asked
Oct 29, 2017
Theory of Computation
theory-of-computation
conjunctive-normal-form
+
–
1
votes
0
answers
17
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?
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 start...
Manu Thakur
4.5k
views
Manu Thakur
asked
Oct 13, 2017
Theory of Computation
theory-of-computation
context-free-language
conjunctive-normal-form
simplification
+
–
1
votes
0
answers
18
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.
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 ...
learner_geek
1.5k
views
learner_geek
asked
Aug 5, 2017
Compiler Design
theory-of-computation
context-free-language
discrete-mathematics
derivation-tree
conjunctive-normal-form
+
–
1
votes
0
answers
19
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
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 no...
learner_geek
4.8k
views
learner_geek
asked
Aug 5, 2017
Theory of Computation
theory-of-computation
derivation-tree
context-free-language
conjunctive-normal-form
+
–
2
votes
1
answer
20
Raghunath Tiwari(NPTEL NOC Chomsky Normal Form)
S->ASB A->aASA | a | ϵ B->SbS | A | bb Convert this grammar into Chomsky Normal Form
S->ASBA->aASA | a | ϵB->SbS | A | bbConvert this grammar into Chomsky Normal Form
Veeplob Singh
828
views
Veeplob Singh
asked
Jul 3, 2017
Theory of Computation
theory-of-computation
context-free-grammar
conjunctive-normal-form
grammar
+
–
1
votes
2
answers
21
Test by Bikram | Mock GATE | Test 2 | Question: 42
The Conjunctive Normal form of a formula $F$ is $(P \vee Q \vee P) \wedge (P \vee Q \vee Q) \wedge (¬P \vee ¬Q \vee ¬P) \wedge (¬P \vee ¬Q \vee ¬Q)$. where, $\wedge$ means AND, $\vee$ means OR Then the value of $F$ is: $T$ $¬(P \wedge Q) \leftrightarrow (P \vee Q)$ $(P \vee Q) \leftrightarrow (P \wedge Q)$ $¬(P \wedge Q) \to (P \vee Q )$
The Conjunctive Normal form of a formula $F$ is$(P \vee Q \vee P) \wedge (P \vee Q \vee Q) \wedge (¬P \vee ¬Q \vee ¬P) \wedge (¬P \vee ¬Q \vee ¬Q)$. where...
Bikram
493
views
Bikram
asked
Jan 24, 2017
GATE
tbb-mockgate-2
discrete-mathematics
mathematical-logic
propositional-logic
conjunctive-normal-form
+
–
2
votes
2
answers
22
[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
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 i...
rahul sharma 5
2.4k
views
rahul sharma 5
asked
Jan 12, 2017
Theory of Computation
theory-of-computation
context-free-language
conjunctive-normal-form
derivation-tree
+
–
0
votes
2
answers
23
TOC CFG to CNF convertion
KISHALAY DAS
1.3k
views
KISHALAY DAS
asked
Dec 10, 2016
Theory of Computation
theory-of-computation
context-free-language
conjunctive-normal-form
+
–
1
votes
0
answers
24
#sipser book
Can ambiguous context free grammar be converted into CNF form..?
Can ambiguous context free grammar be converted into CNF form..?
Abhishekcs10
281
views
Abhishekcs10
asked
Sep 14, 2016
Theory of Computation
context-free-grammar
conjunctive-normal-form
+
–
54
votes
5
answers
25
GATE CSE 2007 | Question: 48
Which of the following is TRUE about formulae in Conjunctive Normal Form? For any formula, there is a truth assignment for which at least half the clauses evaluate to true. For any formula, there is a truth assignment for which all the clauses ... formula such that for each truth assignment, at most one-fourth of the clauses evaluate to true. None of the above.
Which of the following is TRUE about formulae in Conjunctive Normal Form?For any formula, there is a truth assignment for which at least half the clauses evaluate to true...
Kathleen
14.9k
views
Kathleen
asked
Sep 21, 2014
Digital Logic
gatecse-2007
digital-logic
normal
conjunctive-normal-form
+
–
To see more, click for the
full list of questions
or
popular tags
.
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register