# this file requires Python 3
#
# run interpreter: python3 -i kostra0201.py
# typecheck: mypy kostra0201.py
#
# You can do arbitrary modifications, but you are not allowed to add imports,
# manipulate IO, and the signature of generate must be compatible.


example_G = (['S', 'A', 'B'], ['a', 'b'], {
        'S': [('', None), ('a', None), ('a', 'A'), ('b', None), ('b', 'B')],
        'A': [('a', None), ('a', 'A'), ('b', None), ('b', 'B')],
        'B': [('b', None), ('b', 'B')],
    }, 'S')


def generates(g, w):
    nonterms, terms, rules, start = g

    # you can get rules for given nonterminal as follows
    start_rules = rules[start]