{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Regular expressions" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from tock import *" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Regular expressions in Tock use the following operators:\n", "\n", "- `|` or `∪` for union\n", "- concatenation for concatenation\n", "- `*` for Kleene star\n", "\n", "This is very similar to Unix regular expressions, but because a symbol can have more than one character, consecutive symbols must be separated by a space. Also, for the empty string, you must write `ε` (or `&`). The empty set is written as `∅`.\n", "\n", "To create a regular expression from a string (Sipser, Example 1.56):" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/html": [ "(a b ∪ a)*" ], "text/plain": [ "" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "r = RegularExpression.from_str('(a b|a)*')\n", "r" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "However, there isn't much you can do with a `RegularExpression` object other than to convert it to an NFA.\n", "\n", "## From regular expressions to NFAs" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "m = from_regexp(r) # from RegularExpression object\n", "m = from_regexp('(a b|a)*') # a str is automatically parsed into a RegularExpression" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The regular expression is converted into a finite automaton, which you can view, as usual, as either a graph or a table." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "2\n", "\n", "\n", "q8\n", "\n", "\n", "\n", "_START->2\n", "\n", "\n", "\n", "\n", "\n", "0\n", "\n", "q1\n", "\n", "\n", "\n", "1\n", "\n", "q2\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "a\n", "\n", "\n", "\n", "4\n", "\n", "q3\n", "\n", "\n", "\n", "1->4\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "5\n", "\n", "q7\n", "\n", "\n", "\n", "2->5\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "3\n", "\n", "q5\n", "\n", "\n", "\n", "6\n", "\n", "\n", "q6\n", "\n", "\n", "\n", "3->6\n", "\n", "\n", "a\n", "\n", "\n", "\n", "7\n", "\n", "\n", "q4\n", "\n", "\n", "\n", "4->7\n", "\n", "\n", "b\n", "\n", "\n", "\n", "5->0\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "5->3\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "6->5\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "7->5\n", "\n", "\n", "ε\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "to_graph(m)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
εab
q1q2
q2q3
q3q4
@q4q7
q5q6
@q6q7
q7{q1,q5}
>@q8q7
" ], "text/plain": [ "" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "to_table(m)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The states are numbered according to the position in the regular expression they came from (so that listing them in alphabetical order is natural). The letter suffixes are explained below.\n", "\n", "We can also pass the `display_steps=True` option to show the automata created for all the subexpressions." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/html": [ "subexpression: a" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "0\n", "\n", "q1\n", "\n", "\n", "\n", "_START->0\n", "\n", "\n", "\n", "\n", "\n", "1\n", "\n", "\n", "q2\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "a\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "subexpression: b" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "0\n", "\n", "q3\n", "\n", "\n", "\n", "_START->0\n", "\n", "\n", "\n", "\n", "\n", "1\n", "\n", "\n", "q4\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "b\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "subexpression: a b" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "2\n", "\n", "q1\n", "\n", "\n", "\n", "_START->2\n", "\n", "\n", "\n", "\n", "\n", "0\n", "\n", "q2\n", "\n", "\n", "\n", "1\n", "\n", "q3\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "3\n", "\n", "\n", "q4\n", "\n", "\n", "\n", "1->3\n", "\n", "\n", "b\n", "\n", "\n", "\n", "2->0\n", "\n", "\n", "a\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "subexpression: a" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "1\n", "\n", "q5\n", "\n", "\n", "\n", "_START->1\n", "\n", "\n", "\n", "\n", "\n", "0\n", "\n", "\n", "q6\n", "\n", "\n", "\n", "1->0\n", "\n", "\n", "a\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "subexpression: a b ∪ a" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "4\n", "\n", "q7\n", "\n", "\n", "\n", "_START->4\n", "\n", "\n", "\n", "\n", "\n", "0\n", "\n", "q1\n", "\n", "\n", "\n", "1\n", "\n", "q2\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "a\n", "\n", "\n", "\n", "2\n", "\n", "q3\n", "\n", "\n", "\n", "1->2\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "5\n", "\n", "\n", "q4\n", "\n", "\n", "\n", "2->5\n", "\n", "\n", "b\n", "\n", "\n", "\n", "3\n", "\n", "q5\n", "\n", "\n", "\n", "6\n", "\n", "\n", "q6\n", "\n", "\n", "\n", "3->6\n", "\n", "\n", "a\n", "\n", "\n", "\n", "4->0\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "4->3\n", "\n", "\n", "ε\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "subexpression: (a b ∪ a)*" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "3\n", "\n", "\n", "q8\n", "\n", "\n", "\n", "_START->3\n", "\n", "\n", "\n", "\n", "\n", "0\n", "\n", "q1\n", "\n", "\n", "\n", "1\n", "\n", "q2\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "a\n", "\n", "\n", "\n", "2\n", "\n", "q3\n", "\n", "\n", "\n", "1->2\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "7\n", "\n", "\n", "q4\n", "\n", "\n", "\n", "2->7\n", "\n", "\n", "b\n", "\n", "\n", "\n", "5\n", "\n", "q7\n", "\n", "\n", "\n", "3->5\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "4\n", "\n", "q5\n", "\n", "\n", "\n", "6\n", "\n", "\n", "q6\n", "\n", "\n", "\n", "4->6\n", "\n", "\n", "a\n", "\n", "\n", "\n", "5->0\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "5->4\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "6->5\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "7->5\n", "\n", "\n", "ε\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "m = from_regexp('(a b|a)*', display_steps=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## From NFAs to regular expressions\n", "\n", "The `to_regexp` function converts in the opposite direction:" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/html": [ "ε ∪ a* a ∪ (ε ∪ a* a) (a b (ε ∪ a* a))* a b (ε ∪ a* a)" ], "text/plain": [ "" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "e = to_regexp(m)\n", "e" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The resulting regular expression depends a lot on the order in which states are eliminated; Tock eliminates states in reverse alphabetical order.\n", "\n", "Again, the `display_steps` option causes all the intermediate steps of the conversion to be displayed." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "0\n", "\n", "start\n", "\n", "\n", "\n", "_START->0\n", "\n", "\n", "\n", "\n", "\n", "2\n", "\n", "q8\n", "\n", "\n", "\n", "0->2\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "1\n", "\n", "\n", "accept\n", "\n", "\n", "\n", "2->1\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "9\n", "\n", "q7\n", "\n", "\n", "\n", "2->9\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "3\n", "\n", "q1\n", "\n", "\n", "\n", "4\n", "\n", "q2\n", "\n", "\n", "\n", "3->4\n", "\n", "\n", "a\n", "\n", "\n", "\n", "5\n", "\n", "q3\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "7\n", "\n", "q4\n", "\n", "\n", "\n", "5->7\n", "\n", "\n", "b\n", "\n", "\n", "\n", "6\n", "\n", "q5\n", "\n", "\n", "\n", "8\n", "\n", "q6\n", "\n", "\n", "\n", "6->8\n", "\n", "\n", "a\n", "\n", "\n", "\n", "7->1\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "7->9\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "8->1\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "8->9\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "9->3\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "9->6\n", "\n", "\n", "ε\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "eliminate q8" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "0\n", "\n", "start\n", "\n", "\n", "\n", "_START->0\n", "\n", "\n", "\n", "\n", "\n", "1\n", "\n", "\n", "accept\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "8\n", "\n", "q7\n", "\n", "\n", "\n", "0->8\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "2\n", "\n", "q1\n", "\n", "\n", "\n", "3\n", "\n", "q2\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "a\n", "\n", "\n", "\n", "4\n", "\n", "q3\n", "\n", "\n", "\n", "3->4\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "6\n", "\n", "q4\n", "\n", "\n", "\n", "4->6\n", "\n", "\n", "b\n", "\n", "\n", "\n", "5\n", "\n", "q5\n", "\n", "\n", "\n", "7\n", "\n", "q6\n", "\n", "\n", "\n", "5->7\n", "\n", "\n", "a\n", "\n", "\n", "\n", "6->1\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "6->8\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "7->1\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "7->8\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "8->2\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "8->5\n", "\n", "\n", "ε\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "eliminate q7" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "0\n", "\n", "start\n", "\n", "\n", "\n", "_START->0\n", "\n", "\n", "\n", "\n", "\n", "1\n", "\n", "\n", "accept\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "2\n", "\n", "q1\n", "\n", "\n", "\n", "0->2\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "5\n", "\n", "q5\n", "\n", "\n", "\n", "0->5\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "3\n", "\n", "q2\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "a\n", "\n", "\n", "\n", "4\n", "\n", "q3\n", "\n", "\n", "\n", "3->4\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "6\n", "\n", "q4\n", "\n", "\n", "\n", "4->6\n", "\n", "\n", "b\n", "\n", "\n", "\n", "7\n", "\n", "q6\n", "\n", "\n", "\n", "5->7\n", "\n", "\n", "a\n", "\n", "\n", "\n", "6->1\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "6->2\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "6->5\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "7->1\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "7->2\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "7->5\n", "\n", "\n", "ε\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "eliminate q6" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "0\n", "\n", "start\n", "\n", "\n", "\n", "_START->0\n", "\n", "\n", "\n", "\n", "\n", "1\n", "\n", "\n", "accept\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "2\n", "\n", "q1\n", "\n", "\n", "\n", "0->2\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "5\n", "\n", "q5\n", "\n", "\n", "\n", "0->5\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "3\n", "\n", "q2\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "a\n", "\n", "\n", "\n", "4\n", "\n", "q3\n", "\n", "\n", "\n", "3->4\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "6\n", "\n", "q4\n", "\n", "\n", "\n", "4->6\n", "\n", "\n", "b\n", "\n", "\n", "\n", "5->1\n", "\n", "\n", "a\n", "\n", "\n", "\n", "5->2\n", "\n", "\n", "a\n", "\n", "\n", "\n", "5->5\n", "\n", "\n", "a\n", "\n", "\n", "\n", "6->1\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "6->2\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "6->5\n", "\n", "\n", "ε\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "eliminate q5" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "0\n", "\n", "start\n", "\n", "\n", "\n", "_START->0\n", "\n", "\n", "\n", "\n", "\n", "1\n", "\n", "\n", "accept\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "ε ∪ a* a\n", "\n", "\n", "\n", "2\n", "\n", "q1\n", "\n", "\n", "\n", "0->2\n", "\n", "\n", "ε ∪ a* a\n", "\n", "\n", "\n", "3\n", "\n", "q2\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "a\n", "\n", "\n", "\n", "4\n", "\n", "q3\n", "\n", "\n", "\n", "3->4\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "5\n", "\n", "q4\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "b\n", "\n", "\n", "\n", "5->1\n", "\n", "\n", "ε ∪ a* a\n", "\n", "\n", "\n", "5->2\n", "\n", "\n", "ε ∪ a* a\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "eliminate q4" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "0\n", "\n", "start\n", "\n", "\n", "\n", "_START->0\n", "\n", "\n", "\n", "\n", "\n", "1\n", "\n", "\n", "accept\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "ε ∪ a* a\n", "\n", "\n", "\n", "2\n", "\n", "q1\n", "\n", "\n", "\n", "0->2\n", "\n", "\n", "ε ∪ a* a\n", "\n", "\n", "\n", "3\n", "\n", "q2\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "a\n", "\n", "\n", "\n", "4\n", "\n", "q3\n", "\n", "\n", "\n", "3->4\n", "\n", "\n", "ε\n", "\n", "\n", "\n", "4->1\n", "\n", "\n", "b (ε ∪ a* a)\n", "\n", "\n", "\n", "4->2\n", "\n", "\n", "b (ε ∪ a* a)\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "eliminate q3" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "0\n", "\n", "start\n", "\n", "\n", "\n", "_START->0\n", "\n", "\n", "\n", "\n", "\n", "1\n", "\n", "\n", "accept\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "ε ∪ a* a\n", "\n", "\n", "\n", "2\n", "\n", "q1\n", "\n", "\n", "\n", "0->2\n", "\n", "\n", "ε ∪ a* a\n", "\n", "\n", "\n", "3\n", "\n", "q2\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "a\n", "\n", "\n", "\n", "3->1\n", "\n", "\n", "b (ε ∪ a* a)\n", "\n", "\n", "\n", "3->2\n", "\n", "\n", "b (ε ∪ a* a)\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "eliminate q2" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "0\n", "\n", "start\n", "\n", "\n", "\n", "_START->0\n", "\n", "\n", "\n", "\n", "\n", "1\n", "\n", "\n", "accept\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "ε ∪ a* a\n", "\n", "\n", "\n", "2\n", "\n", "q1\n", "\n", "\n", "\n", "0->2\n", "\n", "\n", "ε ∪ a* a\n", "\n", "\n", "\n", "2->1\n", "\n", "\n", "a b (ε ∪ a* a)\n", "\n", "\n", "\n", "2->2\n", "\n", "\n", "a b (ε ∪ a* a)\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "eliminate q1" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "0\n", "\n", "start\n", "\n", "\n", "\n", "_START->0\n", "\n", "\n", "\n", "\n", "\n", "1\n", "\n", "\n", "accept\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "ε ∪ a* a ∪ (ε ∪ a* a) (a b (ε ∪ a* a))* a b (ε ∪ a* a)\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "e = to_regexp(m, display_steps=True)" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.1" } }, "nbformat": 4, "nbformat_minor": 1 }