search
Log In

Recent questions tagged cnf

0 votes
0 answers
1
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 terminal. Show how to convert any grammar into a CNF grammar for the same language (with the possible exception of the empty string - no CNF grammar can generate $\epsilon$).
asked Aug 20, 2019 in Compiler Design Lakshman Patel RJIT 25 views
0 votes
0 answers
2
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 production $S\rightarrow a \:a$ first, then we shall ... following exercises are useful steps in the construction of a "Chomsky Normal Form" grammar from arbitrary grammars, as defined in Question $4.4.8$.
asked Aug 20, 2019 in Compiler Design Lakshman Patel RJIT 47 views
0 votes
1 answer
3
1 vote
1 answer
4
0 votes
1 answer
5
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, 2019 in Theory of Computation Lakshman Patel RJIT 66 views
2 votes
1 answer
6
0 votes
1 answer
7
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$
asked Jul 13, 2018 in Theory of Computation Pooja Khatri 392 views
0 votes
0 answers
8
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 hem chandra joshi 309 views
2 votes
1 answer
9
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 Mk Utkarsh 554 views
1 vote
1 answer
10
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
asked Jan 22, 2018 in Theory of Computation Anshul Shankar 409 views
1 vote
1 answer
11
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 Anjan 389 views
0 votes
0 answers
12
0 votes
1 answer
13
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
asked Nov 25, 2017 in Theory of Computation Surajit 257 views
1 vote
0 answers
15
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 Manu Thakur 677 views
1 vote
0 answers
16
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 Manu Thakur 1.5k views
1 vote
0 answers
17
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 learner_geek 526 views
1 vote
0 answers
18
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 learner_geek 1.7k views
2 votes
1 answer
19
0 votes
1 answer
20
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 rahul sharma 5 357 views
1 vote
0 answers
22
Can ambiguous context free grammar be converted into CNF form..?
asked Sep 14, 2016 in Theory of Computation Abhishekcs10 112 views
To see more, click for the full list of questions or popular tags.
...