parity.ipynb

} }, "cells": [ { "cell_type": "code", "metadata": { "id": "XpM_nHoFnU7Z", "colab": { "base_uri": "https://localhost:8080/" }, "outputId": "660fd23e-0ba3-424b-b114-762920ee95be" }, "source": [ "# MS Branicky, 2019-08-30, 2021-02-09 ", " ", "Q = set(['q0', 'q1']) ", "Sigma = set(\"01\") ", " ", "delta = { # FA that checks even parity ", " ('q0', '0') : 'q0', ", " ('q0', '1') : 'q1', ", " ('q1', '0') : 'q1', ", " ('q1', '1') : 'q0' ", "} ", "s = 'q0' ", "F = set(['q0']) ", " ", "test_inputs = [\"011\", \"0111\"] ", " ", "# ------ YOU SHOULD NOT HAVE TO CHANGE ANYTHING BELOW HERE ------ ", "# consistency and completeness checks on the model aka \"input checking\" ", "assert s in Q, \"s must be in Q\" ", "assert F \ \" + str(state), end=\" \") ", " ", "for input_string in test_inputs: ", " # check input consistency ", " assert set(input_string) ", "q0 --1--> ", "q1 --1--> ", "q0 Accept ", " ", "Start, input = 0111 ", "q0 --0--> ", "q0 --1--> ", "q1 --1--> ", "q0 --1--> ", "q1 Reject ", " " ], "name": "stdout" } ] } ] }

Purpose: Play with DFA implementations. The python notebook parity.ipynb can be used to specify and then simulate DFAs. Specifically, it has defined in it the specification of a machine that detects even-parity binary strings. a. Study the program, play with it, convince yourself of how it works. There is no need to turn any I/O in. Just report any anomalies you might have found. b. Copy the notebook (File -> Save a Copy in Drive) to a new Colab notebook called 510.ipynb (or cut-and-paste to a .py file if you Python installed on your own machine). Modify the definition section to implement a machine recognizing the language "Strings in {0,1,5}* containing the substring 510" given in lecture. Test it as you see fit. Turn in a printout of the modified code section only. C. Repeat part b, but with the alphabet (0,1,2,3,4,5,6,7,8,9). Use an implicit assignment! For example, in C++ an explicit definition of an array is int all {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}; An implicit definition of the same array is for (i=0; i Save a Copy in Drive) to a new Colab notebook called 510.ipynb (or cut-and-paste to a .py file if you Python installed on your own machine). Modify the definition section to implement a machine recognizing the language "Strings in {0,1,5}* containing the substring 510" given in lecture. Test it as you see fit. Turn in a printout of the modified code section only. C. Repeat part b, but with the alphabet (0,1,2,3,4,5,6,7,8,9). Use an implicit assignment! For example, in C++ an explicit definition of an array is int all {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}; An implicit definition of the same array is for (i=0; i