A x B | |

A x y z B | |

A B | |

A x |

As an example of the correspondence between an nfa and a right-linear grammar, the following automaton and grammar both recognize the set of strings consisting of an even number of 0's and an even number of 1's.

S S 0 B S 1 A A 0 C A 1 S B 0 S B 1 C C 0 A C 1 B |

Copyright © 1996 by David Matuszek

Last modified Feb 11, 1996