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 ...
- 333
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 ...
- 275k
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 ...
- 1,304
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 ...
- 11.9k
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 ...
- 275k
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 ...
- 29.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$ ...
- 1,195
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$...
- 8,114
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 ...
- 275k
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.
- 9,757
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 ...
- 29.8k
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 ...
- 275k
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 ...
- 13.9k
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.
...
- 31
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 ...
- 1,191
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 = (-...
- 275k
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$ ...
- 531
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 ...
- 275k
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.
...
- 29.8k
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
...
- 19.4k
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 ...
- 121
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 ...
- 8,114
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 ...
- 29.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 ...
- 81.4k
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 \...
- 987
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.♦
- 156k
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 ...
- 275k
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 ...
- 275k
2
votes
Trying to remove ϵ rules from a formal grammar resulted in L(G) ≠ L(G')
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.
- 1,594
2
votes
Accepted
proof that every sentence obtainable by left-most derivations only when Greibach normal form
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}^*\...
- 11.9k
Only top scored, non community-wiki answers of a minimum length are eligible