{"id":304,"date":"2021-10-12T08:54:12","date_gmt":"2021-10-12T06:54:12","guid":{"rendered":"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/?page_id=304"},"modified":"2025-11-02T21:29:27","modified_gmt":"2025-11-02T20:29:27","slug":"automata-theory-and-formal-languages","status":"publish","type":"page","link":"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/index.php\/en\/courses\/automata-theory-and-formal-languages\/","title":{"rendered":"Automata Theory and Formal Languages"},"content":{"rendered":"\n<p><strong>Plan of classes:<\/strong><\/p>\n\n\n\n<ol><li>Relations (6.X.2025)<\/li><li>Relation induced by language (13.X.2025)<\/li><li>Regular expressions (20.X.2025)<\/li><li>Regular languages (27.X.2025)<\/li><li>Context-free grammars: useless symbols and productions (3.XI.2025)<\/li><li>Context-free grammars: normal forms (13.XI.2025)<\/li><li>Context-free languages (17.XI.2025)<\/li><li>First Test (24.XI.2025)\u00a0<\/li><li>Tuning machines (1.XII.2025)<\/li><li>Multi tape Tuning machines (8.XII.2025)<\/li><li>Nondeterministic Tuning Machines (15.XII.2025)<\/li><li>Linear bounded automaton (22.XII.2025)<\/li><li>Finite automata (12.I.2026)<\/li><li>Types of finite automata (19.I.2026)<\/li><li>Second Test (26.I.2026)<\/li><\/ol>\n\n\n\n<p><strong>Resources:<\/strong><\/p>\n\n\n<style type='text\/css'>\r\n  #mla_gallery-1 {\r\n    margin: auto;\r\n  }\r\n  #mla_gallery-1 .gallery-row {\r\n    float: none;\r\n    margin-top: 10px;\r\n    border-top: 1px solid #ddd;\r\n    text-align: center;\r\n    width: 30.3%;\r\n    \r\n  }\r\n  #mla_gallery-1 .gallery-row td.gallery-icon {\r\n    width: 60;\r\n    height: 60;\r\n    vertical-align: top;\r\norientation:landscape\r\n  }\r\n  #mla_gallery-1 .gallery-row .gallery-icon img {\r\n    border: 2px solid #cfcfcf;\r\n  }\r\n  #mla_gallery-1 .gallery-caption {\r\n    margin-left: 0;\r\n    vertical-align: top;\r\n  }\r\n<\/style><div id='mla_gallery-1' class='gallery galleryid-304 gallery-columns-3 gallery-size-thumbnail'>\r\n<!-- row-open -->\r\n<figure class='gallery-item '>\r\n\t<div class='gallery-icon landscape'>\r\n\t\t<a href='https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2021\/10\/02_Handout_AutomataTheoryFormalLanguages-1.pdf'><img width=\"150\" height=\"116\" src=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2021\/10\/02_Handout_AutomataTheoryFormalLanguages-1-pdf-150x116.jpg\" class=\"attachment-thumbnail size-thumbnail\" alt=\"\" loading=\"lazy\" \/><\/a>\r\n\t<\/div>\r\n\t<figcaption class='wp-caption-text gallery-caption' id='mla_gallery-1-313'>\n\t<a href=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2021\/10\/02_Handout_AutomataTheoryFormalLanguages-1.pdf\" target=\"_blank\" rel=\"noopener\">Regular expressions<\/a>\n\t<\/figcaption><\/figure><figure class='gallery-item '>\r\n\t<div class='gallery-icon landscape'>\r\n\t\t<a href='https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2021\/10\/01_Handout_AutomataTheoryFormalLanguages-1.pdf'><img width=\"150\" height=\"116\" src=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2021\/10\/01_Handout_AutomataTheoryFormalLanguages-1-pdf-150x116.jpg\" class=\"attachment-thumbnail size-thumbnail\" alt=\"\" loading=\"lazy\" \/><\/a>\r\n\t<\/div>\r\n\t<figcaption class='wp-caption-text gallery-caption' id='mla_gallery-1-314'>\n\t<a href=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2021\/10\/01_Handout_AutomataTheoryFormalLanguages-1.pdf\" target=\"_blank\" rel=\"noopener\">Relations<\/a>\n\t<\/figcaption><\/figure><figure class='gallery-item last_in_row'>\r\n\t<div class='gallery-icon landscape'>\r\n\t\t<a href='https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2021\/10\/03_Handout_AutomataTheoryFormalLanguages-1.pdf'><img width=\"150\" height=\"116\" src=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2021\/10\/03_Handout_AutomataTheoryFormalLanguages-1-pdf-150x116.jpg\" class=\"attachment-thumbnail size-thumbnail\" alt=\"\" loading=\"lazy\" \/><\/a>\r\n\t<\/div>\r\n\t<figcaption class='wp-caption-text gallery-caption' id='mla_gallery-1-332'>\n\t<a href=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2021\/10\/03_Handout_AutomataTheoryFormalLanguages-1.pdf\" target=\"_blank\" rel=\"noopener\">Regular languages<\/a>\n\t<\/figcaption><\/figure><br style=\"clear: both\" \/>\r\n<!-- row-open -->\r\n<figure class='gallery-item '>\r\n\t<div class='gallery-icon landscape'>\r\n\t\t<a href='https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2021\/11\/04_Handout_AutomataTheoryFormalLanguages.pdf'><img width=\"150\" height=\"116\" src=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2021\/11\/04_Handout_AutomataTheoryFormalLanguages-pdf-150x116.jpg\" class=\"attachment-thumbnail size-thumbnail\" alt=\"\" loading=\"lazy\" \/><\/a>\r\n\t<\/div>\r\n\t<figcaption class='wp-caption-text gallery-caption' id='mla_gallery-1-340'>\n\t<a href=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2021\/11\/04_Handout_AutomataTheoryFormalLanguages.pdf\" target=\"_blank\" rel=\"noopener\">Context-free grammars<\/a>\n\t<\/figcaption><\/figure><figure class='gallery-item '>\r\n\t<div class='gallery-icon landscape'>\r\n\t\t<a href='https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2021\/11\/05_Handout_AutomataTheoryFormalLanguages-1.pdf'><img width=\"150\" height=\"116\" src=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2021\/11\/05_Handout_AutomataTheoryFormalLanguages-1-pdf-150x116.jpg\" class=\"attachment-thumbnail size-thumbnail\" alt=\"\" loading=\"lazy\" \/><\/a>\r\n\t<\/div>\r\n\t<figcaption class='wp-caption-text gallery-caption' id='mla_gallery-1-347'>\n\t<a href=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2021\/11\/05_Handout_AutomataTheoryFormalLanguages-1.pdf\" target=\"_blank\" rel=\"noopener\">Context-free languages<\/a>\n\t<\/figcaption><\/figure><figure class='gallery-item last_in_row'>\r\n\t<div class='gallery-icon landscape'>\r\n\t\t<a href='https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2021\/12\/08_Handout_AutomataTheoryFormalLanguages.pdf'><img width=\"150\" height=\"116\" src=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2021\/12\/08_Handout_AutomataTheoryFormalLanguages-pdf-150x116.jpg\" class=\"attachment-thumbnail size-thumbnail\" alt=\"\" loading=\"lazy\" \/><\/a>\r\n\t<\/div>\r\n\t<figcaption class='wp-caption-text gallery-caption' id='mla_gallery-1-357'>\n\t<a href=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2021\/12\/08_Handout_AutomataTheoryFormalLanguages.pdf\" target=\"_blank\" rel=\"noopener\">Multi-tape Turing machines<\/a>\n\t<\/figcaption><\/figure><br style=\"clear: both\" \/>\r\n<!-- row-open -->\r\n<figure class='gallery-item '>\r\n\t<div class='gallery-icon landscape'>\r\n\t\t<a href='https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2021\/12\/07_Presentation_AutomataTheoryFormalLanguages.pdf'><img width=\"150\" height=\"116\" src=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2021\/12\/07_Presentation_AutomataTheoryFormalLanguages-pdf-150x116.jpg\" class=\"attachment-thumbnail size-thumbnail\" alt=\"\" loading=\"lazy\" \/><\/a>\r\n\t<\/div>\r\n\t<figcaption class='wp-caption-text gallery-caption' id='mla_gallery-1-358'>\n\t<a href=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2021\/12\/07_Presentation_AutomataTheoryFormalLanguages.pdf\" target=\"_blank\" rel=\"noopener\">Turing machines<\/a>\n\t<\/figcaption><\/figure><figure class='gallery-item '>\r\n\t<div class='gallery-icon landscape'>\r\n\t\t<a href='https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2022\/01\/13_Handout_AutomataTheoryFormalLanguages.pdf'><img width=\"150\" height=\"116\" src=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2022\/01\/13_Handout_AutomataTheoryFormalLanguages-pdf-150x116.jpg\" class=\"attachment-thumbnail size-thumbnail\" alt=\"\" loading=\"lazy\" \/><\/a>\r\n\t<\/div>\r\n\t<figcaption class='wp-caption-text gallery-caption' id='mla_gallery-1-360'>\n\t<a href=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2022\/01\/13_Handout_AutomataTheoryFormalLanguages.pdf\" target=\"_blank\" rel=\"noopener\">Finite automata models<\/a>\n\t<\/figcaption><\/figure><figure class='gallery-item last_in_row'>\r\n\t<div class='gallery-icon landscape'>\r\n\t\t<a href='https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2022\/01\/12_Handout_AutomataTheoryFormalLanguages.pdf'><img width=\"150\" height=\"116\" src=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2022\/01\/12_Handout_AutomataTheoryFormalLanguages-pdf-150x116.jpg\" class=\"attachment-thumbnail size-thumbnail\" alt=\"\" loading=\"lazy\" \/><\/a>\r\n\t<\/div>\r\n\t<figcaption class='wp-caption-text gallery-caption' id='mla_gallery-1-361'>\n\t<a href=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2022\/01\/12_Handout_AutomataTheoryFormalLanguages.pdf\" target=\"_blank\" rel=\"noopener\">Finite automata<\/a>\n\t<\/figcaption><\/figure><br style=\"clear: both\" \/>\r\n<!-- row-open -->\r\n<figure class='gallery-item '>\r\n\t<div class='gallery-icon landscape'>\r\n\t\t<a href='https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2022\/01\/11_Handout_AutomataTheoryFormalLanguages.pdf'><img width=\"150\" height=\"116\" src=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2022\/01\/11_Handout_AutomataTheoryFormalLanguages-pdf-150x116.jpg\" class=\"attachment-thumbnail size-thumbnail\" alt=\"\" loading=\"lazy\" \/><\/a>\r\n\t<\/div>\r\n\t<figcaption class='wp-caption-text gallery-caption' id='mla_gallery-1-362'>\n\t<a href=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2022\/01\/11_Handout_AutomataTheoryFormalLanguages.pdf\" target=\"_blank\" rel=\"noopener\">Push down automata<\/a>\n\t<\/figcaption><\/figure><figure class='gallery-item '>\r\n\t<div class='gallery-icon landscape'>\r\n\t\t<a href='https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2022\/01\/10_Handout_AutomataTheoryFormalLanguages.pdf'><img width=\"150\" height=\"116\" src=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2022\/01\/10_Handout_AutomataTheoryFormalLanguages-pdf-150x116.jpg\" class=\"attachment-thumbnail size-thumbnail\" alt=\"\" loading=\"lazy\" \/><\/a>\r\n\t<\/div>\r\n\t<figcaption class='wp-caption-text gallery-caption' id='mla_gallery-1-363'>\n\t<a href=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2022\/01\/10_Handout_AutomataTheoryFormalLanguages.pdf\" target=\"_blank\" rel=\"noopener\">Nondeterministic Turing machine<\/a>\n\t<\/figcaption><\/figure><figure class='gallery-item last_in_row'>\r\n\t<div class='gallery-icon landscape'>\r\n\t\t<a href='https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2022\/01\/09_Handout_AutomataTheoryFormalLanguages.pdf'><img width=\"150\" height=\"116\" src=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2022\/01\/09_Handout_AutomataTheoryFormalLanguages-pdf-150x116.jpg\" class=\"attachment-thumbnail size-thumbnail\" alt=\"\" loading=\"lazy\" \/><\/a>\r\n\t<\/div>\r\n\t<figcaption class='wp-caption-text gallery-caption' id='mla_gallery-1-364'>\n\t<a href=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/2022\/01\/09_Handout_AutomataTheoryFormalLanguages.pdf\" target=\"_blank\" rel=\"noopener\">Linear bounded automaton<\/a>\n\t<\/figcaption><\/figure><br style=\"clear: both\" \/>\r\n<!-- row-open -->\r\n<figure class='gallery-item '>\r\n\t<div class='gallery-icon landscape'>\r\n\t\t<a href='https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/ATFL_test_example_01.pdf'>ATFL first test example<\/a>\r\n\t<\/div>\r\n\t<figcaption class='wp-caption-text gallery-caption' id='mla_gallery-1-540'>\n\t<a href=\"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/wp-content\/uploads\/ATFL_test_example_01.pdf\" target=\"_blank\" rel=\"noopener\">ATFL first test example<\/a>\n\t<\/figcaption><\/figure><br style=\"clear: both\" \/>\r\n<\/div>\r\n\n","protected":false},"excerpt":{"rendered":"<p>Plan of classes: Relations (6.X.2025) Relation induced by language (13.X.2025) Regular expressions (20.X.2025) Regular languages (27.X.2025) Context-free grammars: useless symbols and productions (3.XI.2025) Context-free grammars: normal forms (13.XI.2025) Context-free languages (17.XI.2025) First Test (24.XI.2025)\u00a0 Tuning machines (1.XII.2025) Multi tape Tuning machines (8.XII.2025) Nondeterministic Tuning Machines (15.XII.2025) Linear bounded automaton (22.XII.2025)&hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":77,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/index.php\/wp-json\/wp\/v2\/pages\/304"}],"collection":[{"href":"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/index.php\/wp-json\/wp\/v2\/comments?post=304"}],"version-history":[{"count":19,"href":"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/index.php\/wp-json\/wp\/v2\/pages\/304\/revisions"}],"predecessor-version":[{"id":578,"href":"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/index.php\/wp-json\/wp\/v2\/pages\/304\/revisions\/578"}],"up":[{"embeddable":true,"href":"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/index.php\/wp-json\/wp\/v2\/pages\/77"}],"wp:attachment":[{"href":"https:\/\/pages.mini.pw.edu.pl\/~lucknerm\/index.php\/wp-json\/wp\/v2\/media?parent=304"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}