Straight-line grammar

Straight-line grammars (SLG) are formal grammars that do not branch (every non-terminal has only one associated production rule) nor loop (if non-terminal A appears in a derivation of B, B does not appear in a derivation of A). Such grammars generate only one sequence, and this property makes them of interest in fields like Kolmogorov complexity, Lossless data compression, Structure discovery and Compressed data structure.

The problem of finding a SLG of minimal size is called the Smallest grammar problem.

Formal Definition

A Grammar G is a SLG iif:

1. for every non-terminal $N$, there is at most one production rule that has $N$ as its left-hand side

2. take the graph $G=<V,E>$, with $V$ the set of non-terminals and $(A,B)\in E$ if $B$ appears at the right-hand side of a production rule for $A$. $G$ must be acyclic.

A SLG in Chomsky normal form is equivalent to a straight-line program. In general, the only type of grammar that are considered are context-free grammar.

A list of algorithms

• Sequitur
• Lempel-Ziv-Welch algorithm creates a context-free grammar in a such deterministic way that it is necessary to store only the start rule of the generated grammar.
• Byte pair encoding

Converting a context-free grammar to Greibach Normal Form and Chomsky normal form using CNF/GNF software

CNF / GNF : is a software make the automatic Convertion of a context-free grammar to:

1- Chomsky normal form grammar (CNF).

2- Greibach normal form grammar (GNF).

and also it show you the new grammar in each of the steps of the transformation.

A- Chomsky normal normal grammar (CNF)

1- reduced grammar.

2- epsilon-free grammar.

3- grammar without cycles and unit rules .

4-CNF.

B-Greibach normal form grammar (GNF).

1- reduced grammar.

2- epsilon-free grammar.

3- without cycles and unit rules.

4- non-left recursive grammar.

5- GNF.

with this application you can have CNF and GNF for any context-free grammar just in few steps.

just run the application and create new project and enter your grammar and click done and you will have :

CNF and GNF grammar and the new grammar in each of the steps of the transformation.

See also

• CNF/GNF
• Chomsky normal form software
• CNF/GNF Homepage
• CNF/GNF download