Recent questions tagged conjunctive-normal-form

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

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

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

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

As the null string belongs to the language generated by the grammar, answer of the following questions should be "none of these"?

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

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

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

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