Recent questions tagged conjunctive-normal-form / GATE Overflow for GATE CSE

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

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

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

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

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

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

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

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

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

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

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

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

0 votes

0 answers

13

Chomsky Normal Form

Sanjay Sharma

801 views

Sanjay Sharma asked Dec 10, 2017

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

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

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

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

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

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

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

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

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

0 votes

2 answers

23

TOC CFG to CNF convertion

KISHALAY DAS

1.3k views

KISHALAY DAS asked Dec 10, 2016

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

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

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