Graphical Interface for Grammars and Automata

Table of contents

  1. Basic Usage
    1. Grammar to Graph
    2. Graph to Grammar
    3. Word Containment
    4. Combined View
  2. Edit Buttons
  3. Quick Menu
  4. Drawing Area
  5. Grammar Buttons
  6. Automaton Buttons

Basic Usage

This Website has three main functionalities:

  1. Converting a type 3 grammar into an equivalent DFA
  2. Converting a DFA/NFA into an equivalent type 3 grammar
  3. Checking if an arbitrary word is contained in the language induced by a type 1 grammar

Grammar to Graph

Creating a grammar

Grammars consist of sets of variables, terminals, productions and starting symbol from the variables. Usage:

  1. A variable can consist of multiple symbols (e.g. ZZ), whereas a terminal may only consist of one symbol
  2. Variable and terminal names can not contain comma "," or dash "|" symbols, as they are used for recognizing the grammar structure
  3. Variables and terminals may not share symbols
  4. Apart from that, variables and terminals can be of any type like characters, numbers or symbols
  5. When putting in multiple variables/terminals, separate them by a comma ",". Whitespaces are ignored
  6. Productions must be filled in the form left side -> right side 1 | right side 2 | ...
  7. For example A->aB or B->cC|aaB
  8. Each production must be put in a new line
  9. The starting symbol must be included in the set of variables
  10. ε-productions can be removed using the button below the input form

Converting into an equivalent finite automaton

When you filled in a valid grammar, press the arrow to convert it into an equivalent automaton. If the grammar you provided is type 3, the conversion will succeed, otherwise not.

The equivalent automaton will be displayed in the drawing area.

Graph to Grammar

Creating a graph

Graphs are created using states and transitions between states using the edit buttons; to enter edit mode, press the edit button.

Converting into a type 3 grammar

  1. By default, auto convert is activated, which means that the equivalent grammar is updated as you draw the automaton
  2. To toggle auto convert, use the check box underneath the conversion arrow in the middle of the screen
  3. When auto convert is not active, you can convert your current graph into an equivalent grammar by clicking the conversion arrow

Word Containment

After creating a grammar, you can enter an arbitrary word and check if it is contained in the language induced by the grammar by clicking "Check". If the grammar contains ε-productions, remove them first.

If the language contains the word you put in, a derivation will be displayed showing how the word can be constructed using the productions.

If the grammar you put in is valid and type 1, you can click "Generate example words" to generate up to 100 words that are also contained in the language.

Combined View

The combined view - as the name suggests - allows you to convert a grammar into an equivalent automaton and vice versa.

So you can create an automaton first and convert it into the equivalent grammar (and manipulate that and regenerate the automaton) or create a grammar and convert it into an automaton (and manipulate that).

To convert the automaton into the equivalent grammar, either click on the arrow pointing to the right or enable auto convert. To convert a grammar into an equivalent automaton, you have to click the arrow pointing to the left.

Edit Buttons

  1. Create State

    To create a state, click on the position where you would like to place it inside the drawing area. The first state created will always be the start state. The start property can however be removed later. The states will be named like "z1", "z2" etc.

  2. Create Transition

    To create a transition, click on the state where you want the transition to begin and drag-and-drop to the state where you want the transition to end. You are then prompted to enter a terminal for this transition. Transitions with the same start and end state can also be created like this

  3. Mark End

    To mark a state as end state, click on that state when 'Mark End' is enabled. End states are marked with a second smaller circle inside the state circle

  4. Delete End

    To unmark a state as end state, click on that state when 'Delete End' is enabled.

  5. Mark start

    To mark a state as start state, click on that state when 'Mark Start' is enabled. Start states are marked with an arrow that points to this state

  6. Delete State/Transition

    To delete a state or transition, click on a state or transition. When highlighted, they will become green

  7. Move State

    To move a state to a new position, simply drag-and-drop the state to its desired location

Quick Menu

The quick menu can be activated by clicking on a state while neither of the edit buttons are active.

The quick menu's buttons are assigned to (clockwise):

  1. Cancel (closes the quick menu)
  2. Delete state
  3. Move state
  4. Mark start
  5. Mark end
  6. Delete end

Drawing Area

  1. Panning the view

    2. To pan the view, make sure you that neither of the edit buttons are active or that edit mode is not active. To pan, drag-and-drop the mouse to adjust the view

  2. Zooming

    3. To zoom in/out use scroll wheel

  3. Quick Menu

    4. For editing the states, you can also use the quick menu

Grammar Buttons

  1. Type

    2. This field displays the type of the grammar you put in (if it's a valid grammar)

  2. Clear

    3. This allows you to clear the form containing the grammar you put in

  3. Copy grammar

    4. This allows you to copy the grammar values for you to paste it into any of the other converters

  4. Paste grammar

    5. This allows you to paste the grammar values you copied

  5. Example grammar

    6. This allows you to insert an exemplary grammar for testing purposes

Automaton Buttons

  1. Edit

    2. This allows you to show (and hide) the edit buttons

  2. Clear

    3. This allows you to clear the automaton you have created, after which you can start over

  3. Make Screenshot

    4. This allows you to take a screenshot of the drawing area. When first using this, you are prompted to allow downloads for this page

  4. Determinize

    5. This applies to algorithm for converting a NFA (non definite finite automaton) into a DFA (definite finite automaton) while maintaining the language induced by the automaton

  5. Determinize Partially

    6. This applies an adapted algorithm that turns an arbitrary NFA into one that

    1. Has one start state
    2. For each state at most one successor using a terminal
  6. Remove ε-transitions

    7. This applies the algorithm that removes the ε-transitions in the automaton

  7. DFA/NFA

    8. This fields indicates whether your created automaton is a DFA or NFA