COMP5361 Assignment 3-Theory of Computation Solved

1. Use the PySimpleAutomata-software to write a program that takes as input a transition table for a DFA or NFA A, and outputs the transition diagram for A. For example, the input could be the automaton A = ({q0, q1, q2}, {0, 1}, δ, q0, {q2}) that has transition table

   δ01

   → q0 {q0,q1} {q0} q1 ∅ {q2}

   ⋆q2 ∅ ∅ The automaton A as a transition diagram:

   0,1

   Start q0 0 q1 1 q2

2. Write a Python program that takes as input the transition table for an NFA A (no ε-transitions), such as the one above, and outputs the transition table and diagram for a DFA B, such that L(A) = L(B). For example, the NFA above should result in output

01

∅∅∅

and

→{q0} {q1 } ⋆{q2 } {q0, q1} ⋆{q0 , q2 } ⋆{q1 , q2 } ⋆{q0, q1, q2}

{q0, q1} ∅
∅
{q0, q1} {q0, q1} ∅

{q0, q1}

{q0 } {q2 }
∅
{q0, q2} {q0 } {q2 } {q0, q2}

10

Start {q0} 0 {q0, q1} 1 {q0, q2} 0

1

Input/Output format

The input/output format is up to the student. You may take and show the information in any format you want. The input/output streams is up to the student as well. For example, you may read from sys.stdin or from a file.

Use of libraries and some built-in python functions

• Any other function, whether built-in or not, that directly simplifies the assignment is not allowed.

What to submit

Using the Moodle system, submit a .zip file that includes:
1. Source code.
2. A .pdf file, explaining your format and how to run your code in few lines.

The format to be followed for submission file is :

<yourname> passign3 <student-id>.zip