org.metasyntactic.math.automata
Class ChomskyNormalForm

java.lang.Object
  |
  +--org.metasyntactic.math.automata.ChomskyNormalForm

public class ChomskyNormalForm

extends java.lang.Object

Constructor Summary

ChomskyNormalForm()
Creates new ChomskyNormalForm

Method Summary

void	toChomskyNormalForm() When working with context-free grammars, it is often convenient to have them in simplified form.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ChomskyNormalForm

public ChomskyNormalForm()

Creates new ChomskyNormalForm

Method Detail

toChomskyNormalForm

public void toChomskyNormalForm()

When working with context-free grammars, it is often convenient to have them in simplified form. One of the simplest and most useful forms is called the Chomsky normal form.

A context-free grammar is in Chomsky normal form if every rule is of the form:

• A → BC
• A → a

where a is any terminal and A, B, and C are any variables - except that B and C may not be the start variable. In addition we permit the rule S → ε, where S is the start variable.