import java.io.*;

// This class contains a main function to execute test cases for 
//   conversion of regular grammars to DFAs and simulation of
//   the resulting DFAs on test input strings.

// It assumes classes Nonterminal, Terminal, Rule, Grammar and DFA,
//   and that the first two have constructors with a string argument,
//   a character argument, and no argument respectively.  The 
//   Grammar class is to have a constructor with no argument
//   (for a grammar without rules), a method addRule that takes
//   a rule and adds it to a grammar, and a method buildDFA()
//   that converts a grammar to a DFA.  The Rule class is to have
//   constructors taking a Nonterminal, a Terminal, and perhaps 
//   another Nonterminal.  The DFA is to have a method
//   testStringAndPrint that takes a string, tests it and prints
//   the result, and returns nothing.

// It assumes that the start state of the grammar is always called "S".


class A5                                                          {

   // the test program
   public static void main(String argv[])                           {
     // reg expr: l(l+n)*
     Grammar g=new Grammar();
     g.addRule(new Rule(new Nonterminal("S"),new Terminal('l'),new Nonterminal("A")));
     g.addRule(new Rule(new Nonterminal("S"),new Terminal('l')));
     g.addRule(new Rule(new Nonterminal("A"),new Terminal('l'),new Nonterminal("A")));
     g.addRule(new Rule(new Nonterminal("A"),new Terminal('l')));
     g.addRule(new Rule(new Nonterminal("A"),new Terminal('n'),new Nonterminal("A")));
     g.addRule(new Rule(new Nonterminal("A"),new Terminal('n')));
     DFA dfa=g.buildDFA();
     dfa.testStringAndPrint("l");
     dfa.testStringAndPrint("ll");
     dfa.testStringAndPrint("ln");
     dfa.testStringAndPrint("lnnn");
     dfa.testStringAndPrint("llnnn");
     dfa.testStringAndPrint("lnnln");
     dfa.testStringAndPrint("lxnnn");
     dfa.testStringAndPrint("nnn");
     dfa.testStringAndPrint("nlnl");
     System.out.println("-------");

     // reg expr: ln*
     g=new Grammar();
     g.addRule(new Rule(new Nonterminal("S"),new Terminal('l'),new Nonterminal("A")));
     g.addRule(new Rule(new Nonterminal("S"),new Terminal('l')));
     g.addRule(new Rule(new Nonterminal("A"),new Terminal('n'),new Nonterminal("A")));
     g.addRule(new Rule(new Nonterminal("A"),new Terminal('n')));
     dfa=g.buildDFA();
    dfa.testStringAndPrint("l");
    dfa.testStringAndPrint("ln");
    dfa.testStringAndPrint("lnnn");
    dfa.testStringAndPrint("ll");
    dfa.testStringAndPrint("nnn");
    dfa.testStringAndPrint("llnnn");
    dfa.testStringAndPrint("lnnln");
    dfa.testStringAndPrint("lxnnn");
     System.out.println("-------");

     // reg expr: in + out + in_out
     g=new Grammar();
     g.addRule(new Rule(new Nonterminal("S"),new Terminal('i'),new Nonterminal("A")));
     g.addRule(new Rule(new Nonterminal("S"),new Terminal('o'),new Nonterminal("B")));
     g.addRule(new Rule(new Nonterminal("A"),new Terminal('n'),new Nonterminal("C")));
     g.addRule(new Rule(new Nonterminal("A"),new Terminal('n')));
     g.addRule(new Rule(new Nonterminal("C"),new Terminal('_'),new Nonterminal("D")));
     g.addRule(new Rule(new Nonterminal("D"),new Terminal('o'),new Nonterminal("B")));
     g.addRule(new Rule(new Nonterminal("B"),new Terminal('u'),new Nonterminal("E")));
     g.addRule(new Rule(new Nonterminal("E"),new Terminal('t')));
     dfa=g.buildDFA();
    dfa.testStringAndPrint("in");
    dfa.testStringAndPrint("out");
    dfa.testStringAndPrint("in_out");
    dfa.testStringAndPrint("in_");
    dfa.testStringAndPrint("out_in");
    dfa.testStringAndPrint("i");
    dfa.testStringAndPrint("on");
     System.out.println("-------");

     // reg expr: dd* + dd*.d*
     g=new Grammar();
    g.addRule(new Rule(new Nonterminal("S"),new Terminal('d'),new Nonterminal("A")));
    g.addRule(new Rule(new Nonterminal("S"),new Terminal('d')));
    g.addRule(new Rule(new Nonterminal("A"),new Terminal('d'),new Nonterminal("A")));
    g.addRule(new Rule(new Nonterminal("A"),new Terminal('d')));
    g.addRule(new Rule(new Nonterminal("A"),new Terminal('.'),new Nonterminal("B")));
    g.addRule(new Rule(new Nonterminal("A"),new Terminal('.')));
    g.addRule(new Rule(new Nonterminal("B"),new Terminal('d'),new Nonterminal("B")));
    g.addRule(new Rule(new Nonterminal("B"),new Terminal('d')));
     dfa=g.buildDFA();
    dfa.testStringAndPrint("d");
    dfa.testStringAndPrint("dd");
    dfa.testStringAndPrint("ddd");
    dfa.testStringAndPrint("dddd");
    dfa.testStringAndPrint("d.d");
    dfa.testStringAndPrint("d.dd");
    dfa.testStringAndPrint("dd.");
    dfa.testStringAndPrint(".dd");
    dfa.testStringAndPrint("d.d.d");
    dfa.testStringAndPrint("dd..dd");
     System.out.println("-------");

     // reg expr:
     //   [-](dd* + dd*.dd*[e[-]dd])
     g=new Grammar();
     g.addRule(new Rule(new Nonterminal("S"),new Terminal('d'),new Nonterminal("A")));
     g.addRule(new Rule(new Nonterminal("S"),new Terminal('d')));
     g.addRule(new Rule(new Nonterminal("S"),new Terminal('-'),new Nonterminal("B")));
     g.addRule(new Rule(new Nonterminal("A"),new Terminal('d'),new Nonterminal("A")));
     g.addRule(new Rule(new Nonterminal("A"),new Terminal('d')));
     g.addRule(new Rule(new Nonterminal("B"),new Terminal('d'),new Nonterminal("A")));
     g.addRule(new Rule(new Nonterminal("B"),new Terminal('d')));
     g.addRule(new Rule(new Nonterminal("A"),new Terminal('.'),new Nonterminal("C")));
     g.addRule(new Rule(new Nonterminal("B"),new Terminal('d')));
     g.addRule(new Rule(new Nonterminal("C"),new Terminal('d'),new Nonterminal("D")));
     g.addRule(new Rule(new Nonterminal("C"),new Terminal('d')));
     g.addRule(new Rule(new Nonterminal("D"),new Terminal('d'),new Nonterminal("D")));
     g.addRule(new Rule(new Nonterminal("D"),new Terminal('d')));
     g.addRule(new Rule(new Nonterminal("D"),new Terminal('e'),new Nonterminal("E")));
     g.addRule(new Rule(new Nonterminal("E"),new Terminal('-'),new Nonterminal("F")));
     g.addRule(new Rule(new Nonterminal("E"),new Terminal('d'),new Nonterminal("H")));
     g.addRule(new Rule(new Nonterminal("F"),new Terminal('d'),new Nonterminal("G")));
     g.addRule(new Rule(new Nonterminal("G"),new Terminal('d')));
     g.addRule(new Rule(new Nonterminal("H"),new Terminal('d')));
     dfa=g.buildDFA();
    dfa.testStringAndPrint("d");
    dfa.testStringAndPrint("dd");
    dfa.testStringAndPrint("ddd");
    dfa.testStringAndPrint("dddd");
    dfa.testStringAndPrint("-d");
    dfa.testStringAndPrint("d.d");
    dfa.testStringAndPrint("-d.d");
    dfa.testStringAndPrint("d.dd");
    dfa.testStringAndPrint("-d.dd");
    dfa.testStringAndPrint("ddd.dd");
    dfa.testStringAndPrint("dd.dedd");
    dfa.testStringAndPrint("-ddd.dde-dd");
    dfa.testStringAndPrint("dd.");
    dfa.testStringAndPrint(".dd");
    dfa.testStringAndPrint("-d.");
    dfa.testStringAndPrint("d-dd");
    dfa.testStringAndPrint("d.d.d");
    dfa.testStringAndPrint("ddedd");
    dfa.testStringAndPrint("d.ded.d");
    dfa.testStringAndPrint("dd.de-d");
    dfa.testStringAndPrint("ddd.ddeddd");
    dfa.testStringAndPrint("dd.ded.dedd");
                                                           }
                                                             }