Skip to main content
Share Your Experience: Take the 2024 Developer Survey
7 votes
Accepted

Is the empty string a terminal symbol?

It's true that, in general, definitions don't include the empty string in the set of "terminals", as there's no need for that (e.g. the production rules for a context-free grammar are defined as a ...
potestasity's user avatar
7 votes
Accepted

Why is the start symbol "not allowed" on the right hand side in Chomsky normal form?

Recall that in Chomsky normal form, we are allowed productions of three forms: Productions of the form $A \to a$. Productions of the form $A \to BC$. The production $S \to \epsilon$. We have to ...
Yuval Filmus's user avatar
7 votes
Accepted

Why do grammars in Chomsky Normal Form have derivations of length 2n-1?

Let $n$ be the length of a string. We start with the (non-terminal) symbol $S$ which has length $n=1$. Using $n - 1$ rules of form $(non-terminal) \rightarrow (non-terminal)(non-terminal)$ we can ...
Auberon's user avatar
  • 1,314
6 votes
Accepted

Convert PEG to BNF

Are the languages recognized by PEGs all context-free? No, as is pointed out by Brian Ford in his 2004 paper introducing PEGs, from which is the following short quote: Theorem: The class of PELs ...
rici's user avatar
  • 12k
5 votes

Is the empty string a terminal symbol?

The empty string is not a terminal symbol. A terminal symbol is an element of the alphabet, but the empty string is not an element of the alphabet. In fact, this is an issue that we have to address ...
Yuval Filmus's user avatar
5 votes

Can every context free grammar be transformed into equivalent grammar of this form?

Yes, you can start with ordinary Greibach NF and replace the offending productions. The trick is the same that is usually used to turn a grammar into Chomsky Normal Form. Introduce new nonterminals ...
Hendrik Jan's user avatar
  • 30.8k
4 votes
Accepted

Write the conjunctive or disjunctive normal form of an expression $f$

As @DavidRicherby said, it's best if you ask who-gave-you-the-question what he meant by $(xyz)_2$. But if you absolutely can not do that, then you look at the situation mathematically as... $(xyz)_2$ ...
Apiwat Chantawibul's user avatar
4 votes
Accepted

When are you supposed to eta-reduce?

Here are some crucial properties about $\beta$ and $\eta$ reductions that explain the strategies for computing normal forms. We write $\rightarrow_\beta, \rightarrow_\eta$ for a single step of $\beta$...
cody's user avatar
  • 8,233
4 votes
Accepted

Trying to remove ϵ rules from a formal grammar resulted in L(G) ≠ L(G')

This question shows the pitfalls of applying algorithms without understanding how they work. There is absolutely no problem with applying an algorithm mechanically, but in that case, you should make ...
Yuval Filmus's user avatar
3 votes

When are you supposed to eta-reduce?

$\eta$ conversion is not a mean to reduce a term to $\beta$-normal form, but a tool to show equivalence regarding the (future) application; to express that 2 terms “are the same function”; that they ...
Sandro Lovnički's user avatar
3 votes

Can any ambiguous context-free grammar be converted into Chomsky normal form?

Any context free grammar can be converted into the equivalent Chomsky Normal Form. It does not matter if it is ambiguous or not.
fade2black's user avatar
  • 9,837
3 votes
Accepted

For every context-free grammar, is there an equivalent grammar in Chomsky normal form?

Depends on how strict you interpret "equivalent". A CFG in ChNF cannot generate the empty string. If you want to have a more precise statement: For every CFG $G$ there is a grammar $G'$ in ChNF ...
Hendrik Jan's user avatar
  • 30.8k
3 votes

Why do grammars in Chomsky Normal Form have derivations of length 2n-1?

Let us consider an simple example. A -> BC B -> b C -> c String to be generated is bc. Then the steps are. ...
Nobin sahu's user avatar
3 votes

Why do grammars in Chomsky Normal Form have derivations of length 2n-1?

And each of the $A \to B C$ produtions make the sentential form one longer. You start with length $1$, to reach $n$ means $n - 1$ steps. If a string has length $n$, there will be $n$ steps to get the ...
vonbrand's user avatar
  • 14.1k
3 votes
Accepted

Converting context-free grammar to Chomsky/Greibach Normal Form

You can convert a context-free grammar into Chomsky normal form or Greibach normal form in whatever way you wish (converting a grammar to a normal form means finding a grammar in the normal form which ...
Yuval Filmus's user avatar
3 votes

Why $\Theta(n^2)$ multiplication of coefficient required for canonical form of polynomial?

Multiplying a degree $d$ polynomial by a degree $1$ monic polynomial requires $d$ multiplications (and some additions). This can be seen from the following formula: $$ (x-c) \sum_{i=0}^d b_i x^i = (-...
Yuval Filmus's user avatar
3 votes
Accepted

Efficiently transforming non-recursive CFG into an NFA

Build a directed graph, with one vertex per non-terminal, and an edge $A \to B$ if there is a rule in the grammar where $A$ is on the left-hand side and $B$ appears on the right-hand side. Since you ...
D.W.'s user avatar
  • 160k
2 votes

What does normalizing with hidden bit really mean?

Shorter Answer (As requested by greybird in the comments) : The gist of "normalizing" in scientific notation, is not to allow the same number to have ...
aderchox's user avatar
  • 121
2 votes

CNF form of variable assignment problem

If you only have to encode this (and don't have any other constraints on $x_i$), you can then use the following constraints: $x_1 < x_2 < \dots < x_{n-1} < x_n \leq k$ which is $n$ ...
MotiNK's user avatar
  • 553
2 votes
Accepted

Is there an algorithm for converting a CFG in Greibach Normal Form into a CFG in strong GNF?

Such an algorithm is described in Koch and Blum, Greibach Normal Form Transformation, Revisited.
Yuval Filmus's user avatar
2 votes

How do I normalize a push down automaton?

What do you call a normalized PDA? There are many ways to specify that. Also, a PDA is defined by its transition fonction. The diagram is just a convenient graphical way to do that, as long as it is ...
babou's user avatar
  • 19.5k
2 votes
Accepted

Identifying/equating constants in a term rewrite system

Counterexample: $f(c) \rightarrow f(d)$ In general, there are some modularity theorems for termination and confluence that may apply if, e.g. your constants do not appear at all in any rule. There ...
cody's user avatar
  • 8,233
2 votes

Why is the start symbol "not allowed" on the right hand side in Chomsky normal form?

All these formalizations are proposed solutions for a problem that can be handled more elegantly. The production $S\to \varepsilon$ is only a trick to indicate that the empty string belongs to the ...
Hendrik Jan's user avatar
  • 30.8k
2 votes
Accepted

Chomsky or Greibach Normal Form?

A context-free grammar is in Chomsky normal form if all productions are of the form $A \to BC$ (where $B,C$ are not the starting symbol), $A \to a$, or $S \to \epsilon$, where $S$ is the starting ...
Yuval Filmus's user avatar
2 votes

Proof any CFG can be converted to GNF

The textbook proofs of Greibach NF I have seen, contain endless substitutions. This way to construct GrNF is much crisper. The key is to understand what the nonterminal $[Y,A]$ actually represents. ...
Hendrik Jan's user avatar
  • 30.8k
2 votes

Context free grammar to Chomsky's normal form

Every context-free grammar can be converted to Chomsky normal form. Also, note that grammars are by definition finite: a grammar might describe infinitely many strings, but the grammar itself is ...
David Richerby's user avatar
2 votes

Finding CNF of $(p \rightarrow q) \rightarrow p$ and $\lnot (q \wedge (\lnot p \rightarrow q)) $

Your formula is incorrect as CNF. Conjunctive normal form (CNF) is a normal form like $$ (a_1 \vee \neg a_2 \vee \dots \vee a_n) \wedge (\neg b_1 \vee \dots \vee b_m) \wedge \dots \wedge (c_1 \vee \...
nekketsuuu's user avatar
2 votes
Accepted

Is there an algorithm for reducing CNFs further?

CNF minimization is hard; see https://cstheory.stackexchange.com/q/9839/5038. It is certainly NP-hard, and there is a sense in which it is "even harder". One way to get some intuition why ...
D.W.'s user avatar
  • 160k
2 votes
Accepted

CYK - finding the closest word accepted

Your problem has been solved by Myers, Approximately Matching Context-Free Languages. A more recent algorithm, together with many relevant pointers, is Rajasekaran and Nicolae, An error correcting ...
Yuval Filmus's user avatar
2 votes

Why add S0 -> S while converting CFG to Chomsky Normal Form

This has to do with the fact that grammars in Chomsky normal form cannot generate the empty word. Indeed, if we only allow rules of the form $A \to BC$ and $A \to a$, then it is impossible to generate ...
Yuval Filmus's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible