Dark Mode

Recent questions tagged conjunctive-normal-form

1 vote

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?

HenryAsks21 asked in Theory of Computation May 2, 2022

357 views

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$).

admin asked in Compiler Design Aug 20, 2019

by admin

312 views

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$.

admin asked in Compiler Design Aug 20, 2019

by admin

484 views

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$.$

admin asked in Theory of Computation May 4, 2019

by admin

581 views

1 vote

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.$

admin asked in Theory of Computation May 4, 2019

by admin

497 views

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$

admin asked in Theory of Computation May 4, 2019

by admin

1.9k views

5 votes

1 answer

7

CONVERT CFG TO GNF
S→ AB A→ BS|b B→ SA|a INTO GNF

Menon Karthik asked in Theory of Computation Dec 14, 2018

by Menon Karthik

26.1k views

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$

Pooja Khatri asked in Theory of Computation Jul 13, 2018

by Pooja Khatri

1.2k views

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 | ε

hem chandra joshi asked in Theory of Computation Apr 10, 2018

by hem chandra joshi

1.3k views

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 $

Mk Utkarsh asked in Theory of Computation Mar 25, 2018

2.7k views

1 vote

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

Anshul Shankar asked in Theory of Computation Jan 22, 2018

by Anshul Shankar

857 views

1 vote

2 answers

12

Chomskey Normal Form
State true/false In CNF , S-> espilon and Start symbol can appear on RHS side of production.

Anjan asked in Theory of Computation Jan 1, 2018

by Anjan

2.9k views

0 votes

0 answers

13

Chomsky Normal Form

Sanjay Sharma asked in Theory of Computation Dec 10, 2017

by Sanjay Sharma

782 views

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

Surajit asked in Theory of Computation Nov 25, 2017

1.1k views

1 vote

1 answer

15

How many variables does the following grammar have when converted to CNF?
E -> E+T E -> T T -> (E) T -> i

gari asked in Theory of Computation Nov 18, 2017

by gari

1.5k views

1 vote

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"?

Manu Thakur asked in Theory of Computation Oct 29, 2017

6.1k views

1 vote

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?

Manu Thakur asked in Theory of Computation Oct 13, 2017

4.4k views

1 vote

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.

learner_geek asked in Compiler Design Aug 5, 2017

by learner_geek

1.5k views

1 vote

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

learner_geek asked in Theory of Computation Aug 5, 2017

by learner_geek

4.7k views

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

Veeplob Singh asked in Theory of Computation Jul 3, 2017

by Veeplob Singh

819 views

1 vote

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 )$

Bikram asked in GATE Jan 24, 2017

by Bikram

481 views

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

rahul sharma 5 asked in Theory of Computation Jan 12, 2017

by rahul sharma 5

2.3k views

0 votes

2 answers

23

TOC CFG to CNF convertion

KISHALAY DAS asked in Theory of Computation Dec 10, 2016

by KISHALAY DAS

1.2k views

1 vote

0 answers

24

#sipser book
Can ambiguous context free grammar be converted into CNF form..?

Abhishekcs10 asked in Theory of Computation Sep 14, 2016

by Abhishekcs10

275 views

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.

Kathleen asked in Digital Logic Sep 21, 2014

14.8k views

To see more, click for the full list of questions or popular tags.

Recent questions tagged conjunctive-normal-form