# Tag Info

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

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

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

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

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

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

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

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

### 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 ...
You already lost the $010$ word when you've removed the $A\to \epsilon$ rule. In $G'$, which is the grammar you got by removing $\epsilon$-rules, you also need to add the $A \to 01$ rule.
The fact that the grammar is in Greibach Normal Form does not contribute to the assertion being proved. For any context-free grammar $G$ with start symbol $S$, \$\omega\in L(G)\iff S\Rightarrow_{lm}^*\...