Laboratory Work Task No. 1 Regular Grammar to Finite Automato

Using Finite Automaton (FA) check if some input string is accepted by FA (meaning you could generate that string by traversing FA).

Accepted string:

String was not accepted:

The task is implemented in 'DFA.py' file.

Laboratory Work Task No. 2 NFA to DFA conversion

Write program which converts nondeterministic finite automato (NFA) to deterministic finite automato (DFA).

Visualisation of the DFA:

Where 1, 2 and 3 are terminal symbols. I wasn't able to implement the self-loops, because it was impossible for me to install pygraphviz package. But this visualisation is possible for every grammar included in the text file.

New transitions and all the rules obtained from transforming an NFA to DFA are stored in a dictionary.

The task is implemented in 'NFAtoDFA.py' file.

Laboratory Work Task No. 3 CFG to CNF conversion

Tasks:

1. Eliminate ε productions.

2. Eliminate any renaming.

3. Eliminate inaccessible symbols.

4. Eliminate the non productive symbols.

5. Obtain the Chomsky Normal Form

Variant No. 26:

The output of the program:

Laboratory Work Task No. 4 LL1 parser

This laboratory work consist of implementing the LL1 parser. Symbol 'e' stays for empty string. The code is implemented in file 'LL1' and the grammar for this work (variant 26) is in the file 'grammar.txt'