API

This part of the documentation covers all the interfaces of angryowl.

Grammar

class angryowl.grammar.Grammar(VN, VT, P, S)

A formal grammar is defined by 4 components:

Parameters:

• VN (set[Hashable]) – set of nonterminals

• VT (set[Hashable]) – set of terminals

• P (dict[SymbolsStr, set[SymbolsStr]]) – list of productions

• S (Hashable) – starting state

The list of productions is represented by a dictionary, each rule being a mapping of a string of symbols onto another string of symbols.

For example, the following formal grammar:

A -> aA
A -> aB
A -> ε
B -> b

Is represented in this way:

Grammar(VN = {"A", "B"},
        VT = {"a", "b"},
        P = {
            ("A",): {("a", "B"), ("a", "A"), ()},
            ("B",): {("b",)}
        },
        S = "A")

SymbolsStr

alias of tuple[Hashable]

production_rules()

Return type:

Generator[tuple[SymbolsStr, SymbolsStr], None, None]

type()

Returns the type of the grammar object according to the Chomsky hierarchy.

If we determine the type of each production rule in the grammar, then the type of the grammar will be the least restrictive type among them (i.e. the minimum number).

Return type:

GrammarType

constr_word()

Assuming a *strictly* regular grammar, construct a word using rules from the grammar picked at random.

Returns:

A random string that is valid according to the grammar.

Return type:

list[collections.abc.Hashable]

to_NFA()

Convert a *strictly* regular grammar to an NFA.

There are 3 forms of production rules in a strictly regular grammar. The algorithm basically executes a list of actions for each production rule:

1. A -> aB

   • a transition is created: (A, a): B

   • “a” is added to the alphabet

2. A -> a

   • a transition is created: (A, a): ε

   • a final state is added: ε

   • “a” is added to the alphabet

3. B -> ε

   • a final state is added: B

For example, the formal grammar:

A -> aA
A -> aB
A -> ε
B -> b

is transformed into the following NFA:

FA( S = {'B', 'ε', 'A'},
    A = {'a', 'b'},
    s0 = 'A',
    d = {('A', 'a'): {'A', 'B'}, ('B', 'b'): {'ε'}},
    F = {'ε', 'A'})

Parameters:

g – A strictly regular grammar.

Returns:

An angryowl.automata.FA instance.

Return type:

FA

to_normal_form()

Convert a context-free grammar to its Chomsky normal form.

Return type:

Grammar

is_in_normal_form()

Check if grammar is in Chomsky normal form.

Return type:

bool

to_latex()

Export to LaTeX string in the widely used grammar notation as a list of four sets.

Return type:

str

class angryowl.grammar.GrammarType(value, names=None, *, module=None, qualname=None, type=None, start=1, boundary=None)

Grammar classes according to the Chomsky hierarchy.

UNRESTRICTED = 0

CONTEXT_SENSITIVE = 1

CONTEXT_FREE = 2

REGULAR = 3

Automata

class angryowl.automata.FA(S, A, s0, d, F)

A formal automaton is represented by 5 variables.

Parameters:

• S (set[Hashable]) – set of states

• A (set[Hashable]) – alphabet (set of symbols)

• s0 (Hashable) – initial state

• d (dict[tuple[set[Hashable], Hashable], set[Hashable]]) – the state-transition function

• F (set[Hashable]) – set of final states

is_deterministic()

See what determinism means on wikipedia.

Returns:

True if the FA is deterministic, otherwise False.

Return type:

bool

verify(w)

Assuming the automaton is deterministic, verify whether it accepts the given string.

Returns:

True if string is accepted, otherwise False.

Parameters:

w (Iterable[Hashable]) –

Return type:

bool

to_grammar()

Convert the FA to a regular grammar.

Returns:

a strictly regular grammar corresponding to the current FA.

Return type:

Grammar

to_DFA()

If this FA is nondeterministic, convert it to a deterministic one.

Basically, the states in the NFA become sets of states in the DFA. For a better explanation of the algorithm see the Dragon book.

For example, the NFA:

FA( S = {'B', 'ε', 'A'},
    A = {'a', 'b'},
    s0 = 'A',
    d = {('A', 'a'): {'A', 'B'}, ('B', 'b'): {'ε'}},
    F = {'ε', 'A'})

is transformed into the following DFA:

FA( S = {{'A'}, {'A', 'B'}, {'ε'}},
    A = {'a', 'b'},
    s0 = {'A'},
    d = {
        ({'A'}, 'a'): {{'A', 'B'}},
        ({'A', 'B'}, 'a'): {{'A', 'B'}},
        ({'A', 'B'}, 'b'): {{'ε'}}
    },
    F = {{'A'}, {'A', 'B'}, {'ε'}})

Return type:

FA

draw(dirname, name)

Export the FA to a diagram in SVG using graphviz.

Parameters:

• dirname (str) – Directory in which the file will be created.

• name (str) – Name of the diagram, which will become the filename.

Returns:

Full path of the exported file.

Return type:

str