{"id":13860,"date":"2014-12-15T14:14:00","date_gmt":"2014-12-15T13:14:00","guid":{"rendered":"https:\/\/rafen.app\/uncategorized\/the-theory-of-algorithms-automata-and-languages\/"},"modified":"2023-06-06T18:20:19","modified_gmt":"2023-06-06T17:20:19","slug":"the-theory-of-algorithms-automata-and-languages","status":"publish","type":"post","link":"https:\/\/raf.edu.rs\/en\/subjects\/the-theory-of-algorithms-automata-and-languages\/","title":{"rendered":"The theory of algorithms, automata and languages"},"content":{"rendered":"<h5>Objectives and outcomes<\/h5>\n<p>Acquiring general and professional knowledge of the theory of algorithms, automata and languages. \u200b\u200bStudents will acquire important concepts and knowledge of the theory of algorithms, automata and languages \u200b\u200b- about deterministic and non-deterministic finite automata, regular expressions and regular languages, properties of regular languages, context-free grammars and languages, automata, properties of context-free languages, Turing machine, classes of problems of polynomial and exponential complexity.<\/p>\n<h5>Lectures<\/h5>\n<p>Alphabets. Strings and languages over an alphabet. Formal grammars. Language of a grammar. Chomsky\u2019s hierarchy of formal grammars. Deterministic finite automata. Transition function, extended transition function and language of an DFA. Nondeterministic finite automata. Extended transition function and language of an NFA. Equivalence of DFA and NFA, construction by subsets method.<br \/>\nNondeterministic finite automata with empty strings (\u025b &#8211; NFA). Extended transition function and language of an \u025b &#8211; NFA. Equivalence of \u025b &#8211; NFA and DFA. Regular expressions. Finite automata and regular expressions. Equivalence of regular expressions and DFA in terms of formalism. Construction of a regular expression upon a DFA. Construction of a DFA upon a regular expression.<br \/>\nUse of regular expressions \u2013 lexical analysis. Regular languages. Pumping lemma. Equivalence and minimisation of automata. Minimisation of DFA. Context-free grammars. Derivations. Language determined by grammar. Derivation tree. Use of context-free grammars. Parsers. Pushdown automata. Acceptance by a final state. Acceptance by an empty stack. Equivalence of context-free<br \/>\ngrammars and pushdown automata. Deterministic pushdown automata. Properties of context-free languages. Chomsky\u2019s normal form for context-free grammars. Pumping lemma for context-free languages. Testing whether a given word belongs to a given context-free language. Turing machine. Multi-tape Turing machine. Nondeterministic Turing machine. Recursively enumerable and recursive languages. Classes P and NP. NP \u2013complete problems. Proof of NP-completeness for CSAT and 3SAT.<\/p>\n<h5>Practical classes<\/h5>\n<p>In lectures, theory is supported by characteristic examples for easier understanding. Practical classes follow the lectures.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Objectives and outcomes Acquiring general and professional knowledge of the theory of algorithms, automata and languages. \u200b\u200bStudents will acquire important concepts and knowledge of the theory of algorithms, automata and languages \u200b\u200b- about deterministic and &#8230; <a title=\"The theory of algorithms, automata and languages\" class=\"read-more\" href=\"https:\/\/raf.edu.rs\/en\/subjects\/the-theory-of-algorithms-automata-and-languages\/\" aria-label=\"More on The theory of algorithms, automata and languages\">Read more<\/a><\/p>\n <a href=\"https:\/\/raf.edu.rs\/en\/subjects\/the-theory-of-algorithms-automata-and-languages\/\" class=\"more-link\" title=\"Read more\">Read more<\/a>","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[199],"tags":[],"class_list":["post-13860","post","type-post","status-publish","format-standard","hentry","category-subjects"],"acf":[],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.7 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>The theory of algorithms, automata and languages - School of Computing<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/raf.edu.rs\/en\/subjects\/the-theory-of-algorithms-automata-and-languages\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"The theory of algorithms, automata and languages - School of Computing\" \/>\n<meta property=\"og:description\" content=\"Objectives and outcomes Acquiring general and professional knowledge of the theory of algorithms, automata and languages. \u200b\u200bStudents will acquire important concepts and knowledge of the theory of algorithms, automata and languages \u200b\u200b- about deterministic and ... Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/raf.edu.rs\/en\/subjects\/the-theory-of-algorithms-automata-and-languages\/\" \/>\n<meta property=\"og:site_name\" content=\"School of Computing\" \/>\n<meta property=\"article:published_time\" content=\"2014-12-15T13:14:00+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2023-06-06T17:20:19+00:00\" \/>\n<meta name=\"author\" content=\"RAF Admin\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"RAF Admin\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/subjects\\\/the-theory-of-algorithms-automata-and-languages\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/subjects\\\/the-theory-of-algorithms-automata-and-languages\\\/\"},\"author\":{\"name\":\"RAF Admin\",\"@id\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/#\\\/schema\\\/person\\\/4e2166c781f2802c67414a1578c66a43\"},\"headline\":\"The theory of algorithms, automata and languages\",\"datePublished\":\"2014-12-15T13:14:00+00:00\",\"dateModified\":\"2023-06-06T17:20:19+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/subjects\\\/the-theory-of-algorithms-automata-and-languages\\\/\"},\"wordCount\":308,\"publisher\":{\"@id\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/#organization\"},\"articleSection\":[\"Subjects\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/subjects\\\/the-theory-of-algorithms-automata-and-languages\\\/\",\"url\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/subjects\\\/the-theory-of-algorithms-automata-and-languages\\\/\",\"name\":\"The theory of algorithms, automata and languages - School of Computing\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/#website\"},\"datePublished\":\"2014-12-15T13:14:00+00:00\",\"dateModified\":\"2023-06-06T17:20:19+00:00\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/subjects\\\/the-theory-of-algorithms-automata-and-languages\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/raf.edu.rs\\\/en\\\/subjects\\\/the-theory-of-algorithms-automata-and-languages\\\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/subjects\\\/the-theory-of-algorithms-automata-and-languages\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Homepage\",\"item\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Subjects\",\"item\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/subjects\\\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"The theory of algorithms, automata and languages\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/#website\",\"url\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/\",\"name\":\"School of Computing\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/#organization\",\"name\":\"School of Computing\",\"url\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/#\\\/schema\\\/logo\\\/image\\\/\",\"url\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/wp-content\\\/uploads\\\/2023\\\/02\\\/cropped-raf-engleski.png\",\"contentUrl\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/wp-content\\\/uploads\\\/2023\\\/02\\\/cropped-raf-engleski.png\",\"width\":400,\"height\":66,\"caption\":\"School of Computing\"},\"image\":{\"@id\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/#\\\/schema\\\/logo\\\/image\\\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/#\\\/schema\\\/person\\\/4e2166c781f2802c67414a1578c66a43\",\"name\":\"RAF Admin\",\"sameAs\":[\"https:\\\/\\\/raf.app\"],\"url\":\"https:\\\/\\\/raf.edu.rs\\\/en\\\/author\\\/rafadmin\\\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"The theory of algorithms, automata and languages - School of Computing","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/raf.edu.rs\/en\/subjects\/the-theory-of-algorithms-automata-and-languages\/","og_locale":"en_US","og_type":"article","og_title":"The theory of algorithms, automata and languages - School of Computing","og_description":"Objectives and outcomes Acquiring general and professional knowledge of the theory of algorithms, automata and languages. \u200b\u200bStudents will acquire important concepts and knowledge of the theory of algorithms, automata and languages \u200b\u200b- about deterministic and ... Read more","og_url":"https:\/\/raf.edu.rs\/en\/subjects\/the-theory-of-algorithms-automata-and-languages\/","og_site_name":"School of Computing","article_published_time":"2014-12-15T13:14:00+00:00","article_modified_time":"2023-06-06T17:20:19+00:00","author":"RAF Admin","twitter_card":"summary_large_image","twitter_misc":{"Written by":"RAF Admin","Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/raf.edu.rs\/en\/subjects\/the-theory-of-algorithms-automata-and-languages\/#article","isPartOf":{"@id":"https:\/\/raf.edu.rs\/en\/subjects\/the-theory-of-algorithms-automata-and-languages\/"},"author":{"name":"RAF Admin","@id":"https:\/\/raf.edu.rs\/en\/#\/schema\/person\/4e2166c781f2802c67414a1578c66a43"},"headline":"The theory of algorithms, automata and languages","datePublished":"2014-12-15T13:14:00+00:00","dateModified":"2023-06-06T17:20:19+00:00","mainEntityOfPage":{"@id":"https:\/\/raf.edu.rs\/en\/subjects\/the-theory-of-algorithms-automata-and-languages\/"},"wordCount":308,"publisher":{"@id":"https:\/\/raf.edu.rs\/en\/#organization"},"articleSection":["Subjects"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/raf.edu.rs\/en\/subjects\/the-theory-of-algorithms-automata-and-languages\/","url":"https:\/\/raf.edu.rs\/en\/subjects\/the-theory-of-algorithms-automata-and-languages\/","name":"The theory of algorithms, automata and languages - School of Computing","isPartOf":{"@id":"https:\/\/raf.edu.rs\/en\/#website"},"datePublished":"2014-12-15T13:14:00+00:00","dateModified":"2023-06-06T17:20:19+00:00","breadcrumb":{"@id":"https:\/\/raf.edu.rs\/en\/subjects\/the-theory-of-algorithms-automata-and-languages\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/raf.edu.rs\/en\/subjects\/the-theory-of-algorithms-automata-and-languages\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/raf.edu.rs\/en\/subjects\/the-theory-of-algorithms-automata-and-languages\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Homepage","item":"https:\/\/raf.edu.rs\/en\/"},{"@type":"ListItem","position":2,"name":"Subjects","item":"https:\/\/raf.edu.rs\/en\/subjects\/"},{"@type":"ListItem","position":3,"name":"The theory of algorithms, automata and languages"}]},{"@type":"WebSite","@id":"https:\/\/raf.edu.rs\/en\/#website","url":"https:\/\/raf.edu.rs\/en\/","name":"School of Computing","description":"","publisher":{"@id":"https:\/\/raf.edu.rs\/en\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/raf.edu.rs\/en\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/raf.edu.rs\/en\/#organization","name":"School of Computing","url":"https:\/\/raf.edu.rs\/en\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/raf.edu.rs\/en\/#\/schema\/logo\/image\/","url":"https:\/\/raf.edu.rs\/en\/wp-content\/uploads\/2023\/02\/cropped-raf-engleski.png","contentUrl":"https:\/\/raf.edu.rs\/en\/wp-content\/uploads\/2023\/02\/cropped-raf-engleski.png","width":400,"height":66,"caption":"School of Computing"},"image":{"@id":"https:\/\/raf.edu.rs\/en\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/raf.edu.rs\/en\/#\/schema\/person\/4e2166c781f2802c67414a1578c66a43","name":"RAF Admin","sameAs":["https:\/\/raf.app"],"url":"https:\/\/raf.edu.rs\/en\/author\/rafadmin\/"}]}},"_links":{"self":[{"href":"https:\/\/raf.edu.rs\/en\/wp-json\/wp\/v2\/posts\/13860","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/raf.edu.rs\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/raf.edu.rs\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/raf.edu.rs\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/raf.edu.rs\/en\/wp-json\/wp\/v2\/comments?post=13860"}],"version-history":[{"count":3,"href":"https:\/\/raf.edu.rs\/en\/wp-json\/wp\/v2\/posts\/13860\/revisions"}],"predecessor-version":[{"id":17170,"href":"https:\/\/raf.edu.rs\/en\/wp-json\/wp\/v2\/posts\/13860\/revisions\/17170"}],"wp:attachment":[{"href":"https:\/\/raf.edu.rs\/en\/wp-json\/wp\/v2\/media?parent=13860"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/raf.edu.rs\/en\/wp-json\/wp\/v2\/categories?post=13860"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/raf.edu.rs\/en\/wp-json\/wp\/v2\/tags?post=13860"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}