#!/usr/bin/env python
import sys

# Erzeuge Liste von Regel Tupeln aus String v
# z.B. v='S->aS' ergibt [('S', 'aS')]
def getGramma(v):
   rls = [];
   for rule in v.split(','):
      rule = rule.strip();
      (left, arrow, right) = rule.partition('->');
      rls.append((left.strip(),right.strip()));
   return rls

# Diese Funktion testet ob w in L(G) ist
def wordproblem(G, w):
   # SForms ist die Liste der entwickelten Satzformen
   States = set()
   States.add('S')
   print States
   Steps = 0;
   n = len(w);
   print Steps
   # Die String Indices sind 0 basiert
   while (Steps <= (n - 1)):
      # Leite ab w[Steps] bezeichnet das Step-te Zeichen in w
      States = res(G, States, w[Steps])
      print States
      # Erhoehe Zaehler der Ableitungsschritte S ist Schritt 0
      Steps += 1;
   
   for State in States:
      if (State, w[Steps - 1]) in G:
         return True;

   return False

# Diese Funktion generiert alle Ableitungen die die Regeln in G
# erlauben und die dabei das aktuell Betrachtete Zeichen von
# von w erzeugen.
def res(G, States, Tw):
   NewStates = set();
   for State in States:
      for (left, right) in G:
         if (left == State) and (right[0] == Tw):
            if (len(right) == 2):
               NewStates.add(right[1]);
   return NewStates;


print getGramma(sys.argv[1])
G = getGramma(sys.argv[1]);
print wordproblem(G, sys.argv[2]);