Skip to content

Instantly share code, notes, and snippets.

@sanchezcarlosjr

sanchezcarlosjr/Regular operations.ipynb Secret

Last active February 9, 2022 05:34
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save sanchezcarlosjr/747e1e2c099e7fe1e70b5d5c7b6e2abe to your computer and use it in GitHub Desktop.
Save sanchezcarlosjr/747e1e2c099e7fe1e70b5d5c7b6e2abe to your computer and use it in GitHub Desktop.
Download ZIP
Regular operations.ipynb
Display the source blob
Display the rendered blob
Raw
Regular operations.ipynb
{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"colab": {
"name": "Regular operations.ipynb",
"provenance": [],
"collapsed_sections": [],
"authorship_tag": "ABX9TyNnXyANfXWeENjUAq23NL3v",
"include_colab_link": true
},
"kernelspec": {
"name": "python3",
"display_name": "Python 3"
},
"language_info": {
"name": "python"
}
},
"cells": [
{
"cell_type": "markdown",
"metadata": {
"id": "view-in-github",
"colab_type": "text"
},
"source": [
"<a href=\"https://colab.research.google.com/gist/sanchezcarlosjr/747e1e2c099e7fe1e70b5d5c7b6e2abe/untitled2.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
]
},
{
"cell_type": "markdown",
"source": [
"\n",
"# 1 Regular languages\n",
"## Regular operations\n",
"\n",
"By [Carlos Eduardo Sanchez Torres](https://twitter.com/CharllierJr)\n",
"\n",
"[Introduction to the Theory of Computation](https://sanchezcarlosjr.notion.site/Introduction-to-the-Theory-of-Computation-1c30797e35f64e578e0c1961999ac6fe)"
],
"metadata": {
"id": "pNmfagxRjTqi"
}
},
{
"cell_type": "code",
"source": [
"from collections.abc import MutableSet\n",
"\n",
"# '' == lambda == epsilon (empty string)\n",
"class Language(MutableSet):\n",
" def __init__(self, data: set=set()):\n",
" self.elements = data\n",
"\n",
" def __repr__(self) -> str:\n",
" return str(self.elements)\n",
"\n",
" def __contains__(self, x):\n",
" return x in self.elements \n",
" \n",
" def __iter__(self):\n",
" return iter(self.elements)\n",
" \n",
" def __len__(self):\n",
" return len(self.elements)\n",
"\n",
" def union(self, language: Language):\n",
" return Language(self.elements.union(language.elements))\n",
"\n",
" def intersection(self,language: Language):\n",
" return Language(self.elements.intersection(language.elements))\n",
"\n",
" def concatenation(self, language: Language):\n",
" newLanguage = Language()\n",
" for aSymbol in self.elements:\n",
" for bSymbol in language.elements:\n",
" newLanguage = newLanguage.add(aSymbol+bSymbol)\n",
" return newLanguage\n",
"\n",
" def __mul__(self, other):\n",
" return self.concatenation(other)\n",
"\n",
" def concatenation_itself(self,power: int):\n",
" if power == 0:\n",
" return Language({''})\n",
" if power == 1:\n",
" return self\n",
" language = Language(self.elements)\n",
" for i in range(1,power):\n",
" language = language.concatenation(self)\n",
" return language\n",
"\n",
" def __str__(self):\n",
" return str(self.elements).replace('\\'','').replace('{,','{\\lambda,').replace('{','\\{').replace('}','\\}')\n",
" \n",
" def kleene_star(self, power: int):\n",
" language = Language()\n",
" for i in range(0,power+1):\n",
" language = language.union(self.concatenation_itself(i))\n",
" return language\n",
"\n",
" def __pow__(self, power: int):\n",
" return self.kleene_star(power)\n",
" \n",
" def add(self, element):\n",
" newSet = self.elements.copy()\n",
" newSet.add(element)\n",
" return Language(newSet)\n",
" \n",
" def discard(self,element):\n",
" newSet = self.elements.copy()\n",
" newSet.discard(element)\n",
" return Language(newSet)\n",
"\n"
],
"metadata": {
"id": "N_qup5ZFtBz5"
},
"execution_count": null,
"outputs": []
},
{
"cell_type": "code",
"source": [
"A=Language({'good','bad'})\n",
"B=Language({'boy','girl'})\n",
"assert A.union(B) == {'good', 'bad', 'boy', 'girl'}\n",
"assert A.concatenation(B) == {'goodboy', 'goodgirl', 'badboy', 'badgirl'}\n",
"assert A * B == {'goodboy', 'goodgirl', 'badboy', 'badgirl'}"
],
"metadata": {
"id": "K_CGue3auMxd"
},
"execution_count": null,
"outputs": []
},
{
"cell_type": "code",
"source": [
"A=Language({'good','bad'})\n",
"assert A.concatenation_itself(0) == {''}\n",
"assert A.concatenation_itself(1) == {'good','bad'}\n",
"assert A.concatenation_itself(2) == {'goodgood','goodbad','badgood', 'badbad'}"
],
"metadata": {
"id": "J7YcT1Yn4uke"
},
"execution_count": null,
"outputs": []
},
{
"cell_type": "code",
"source": [
"A=Language({'good','bad'})\n",
"assert A.kleene_star(0) == {''}\n",
"assert A ** 0 == {''}\n",
"assert A.kleene_star(1) == {'', 'good','bad'}\n",
"assert A ** 1 == {'', 'good','bad'}\n",
"assert A.kleene_star(2) == {'','good','bad','goodgood', 'goodbad','badgood', 'badbad'}\n",
"assert A ** 2 == {'','good','bad','goodgood', 'goodbad','badgood', 'badbad'}"
],
"metadata": {
"id": "bJTRx6QDrBDz"
},
"execution_count": null,
"outputs": []
},
{
"cell_type": "code",
"source": [
"A=Language({'a','b'})\n",
"B=Language({'b','c'})\n",
"print(A.kleene_star(3))\n",
"print(Language(A.kleene_star(2).concatenation(B.kleene_star(2))))"
],
"metadata": {
"id": "2jxkIrU6qCV-",
"outputId": "0257c62c-b531-4d6f-87dd-2d403e79452b",
"colab": {
"base_uri": "https://localhost:8080/"
}
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"\\{\\lambda, baa, bab, aaa, bba, bb, ab, aba, abb, aa, bbb, a, aab, b, ba\\}\n",
"\\\\{\\lambda, babc, aa, abcc, bbb, aac, aacb, ac, bcb, aab, acb, abbb, aabc, b, c, abbc, bacc, ba, bbcb, aabb, bab, ab, bbc, bac, bbbc, bbbb, abb, cb, bacb, bbcc, bcc, aacc, bb, bc, cc, abcb, a, abc, acc, babb\\\\}\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"A=Language({'a','b'})\n",
"B=Language({'b','c'})\n",
"print(Language(A.concatenation(B)))\n",
"print(Language(A.concatenation(B)).kleene_star(2))"
],
"metadata": {
"id": "herV14Hv9Klz",
"outputId": "6bfa606c-8518-4507-ca29-ac30ce00d36b",
"colab": {
"base_uri": "https://localhost:8080/"
}
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"\\\\{bc, bb, ab, ac\\\\}\n",
"\\{\\lambda, abac, ab, bbbc, bcbc, bbbb, bbab, abab, acbc, acac, ac, bcab, bcac, bb, abbb, bc, bbac, acab, acbb, abbc, bcbb\\}\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"A=Language({'a','b'})\n",
"B=Language({'b','c'})\n",
"print(Language(A.union(B)))\n",
"print(Language(A.union(B)).kleene_star(2))"
],
"metadata": {
"id": "tVBsl4aY-C0t",
"outputId": "650749ca-df89-45e2-b7c8-ebc20820f5fd",
"colab": {
"base_uri": "https://localhost:8080/"
}
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"\\\\{b, c, a\\\\}\n",
"\\{\\lambda, bb, ab, bc, aa, cb, cc, ca, c, a, ac, b, ba\\}\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"A=Language({'a','b'})\n",
"B=Language({'b','c'})\n",
"print(Language(A.intersection(B)))\n",
"print(Language(A.intersection(B)).kleene_star(5))"
],
"metadata": {
"id": "nwG964FtACMs",
"outputId": "bb433866-25a9-4b2b-a926-c6189d0a8d85",
"colab": {
"base_uri": "https://localhost:8080/"
}
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"\\\\{b\\\\}\n",
"\\{\\lambda, bbb, bbbbb, bb, b, bbbb\\}\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"A=Language({'a','b'})\n",
"B=Language({'b','c'})\n",
"print(Language(Language(A.union(B)).kleene_star(2).concatenation(Language(A.concatenation(B)))))"
],
"metadata": {
"id": "URK5vwvPE0hJ",
"outputId": "65462f57-8bfa-4102-96f9-564b3257ba2f",
"colab": {
"base_uri": "https://localhost:8080/"
}
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"\\\\{abac, cac, babc, abab, acbc, ccbc, caac, bbb, aac, cbbc, ac, cbb, aab, cbac, bcac, cab, abbb, aabc, cbc, ccab, bbac, cabb, caab, abbc, ccbb, aabb, bab, baac, ab, cabc, bbc, bbbc, bcbc, bbbb, bbab, cbbb, abb, acac, bac, aaac, cbab, baab, ccac, bcab, bb, bc, aaab, acab, acbb, bcbb, abc, babb\\\\}\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"A=Language({'a','b'})\n",
"B=Language({'b','c'})\n",
"print(Language(Language(A.kleene_star(2).union(Language(A.concatenation(B)))).concatenation(Language(A.union(B.kleene_star(2))))))"
],
"metadata": {
"id": "wbXvmOG_GhpS",
"outputId": "aeea54f0-b68f-4bb2-f94f-571eda8c1a1a",
"colab": {
"base_uri": "https://localhost:8080/"
}
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"\\\\{\\lambda, aaa, aba, babc, aa, abcc, acbc, bbb, aacb, aac, aab, ac, bcb, bca, acb, baa, abbb, aabc, accb, c, abbc, bccb, bacc, aca, aabb, bbcb, ba, bab, bba, ab, bbc, bbbc, bcbc, abb, bbbb, cb, abc, bac, accc, bccc, bacb, bbcc, bcc, aacc, bb, bc, cc, abcb, acbb, bcbb, a, b, acc, babb\\\\}\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"A=Language({'1','2'})\n",
"B=Language({'b','c'})\n",
"C=Language({'a'})\n",
"print(A.concatenation(Language(B.kleene_star(2).intersection(C.kleene_star(2)))))\n",
"print(Language(A.concatenation(B.kleene_star(2))).intersection(Language(A.concatenation(C.kleene_star(2)))))"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "8fcTIaSmhGBx",
"outputId": "3b61e60b-9816-4e1a-eb0d-9af2a8819d83"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"\\{2, 1\\}\n",
"\\\\{2, 1\\\\}\n"
]
}
]
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment