{"id":7959,"date":"2020-11-17T15:35:29","date_gmt":"2020-11-17T15:35:29","guid":{"rendered":"http:\/\/onlineclassesguru.com\/?p=7959"},"modified":"2020-11-17T15:35:29","modified_gmt":"2020-11-17T15:35:29","slug":"dfsa-equivalence-checker-write-a-well-structured-program-for-checking-equivalence-of-dfsas-automata","status":"publish","type":"post","link":"https:\/\/onlineclassesguru.com\/index.php\/2020\/11\/17\/dfsa-equivalence-checker-write-a-well-structured-program-for-checking-equivalence-of-dfsas-automata\/","title":{"rendered":"DFSA Equivalence Checker-Write a well-structured program for checking equivalence of DFSA\u2019s-Automata"},"content":{"rendered":"<style type=\"text\/css\"><\/style><p>Deterministic Finite State Acceptors play many important roles in computing applications such as compiler design and regular language equivalence testing (the task of determining whether or not two regular languages are indeed the same despite their different looks). And, in certain cases, it is not only convenient but critical that they employ the minimum possible number of states.<\/p>\n<p>Luckily, there are some simple and efficient procedures to reduce\/minimize the number of states in a DFA such as methods \u201cMark\u201d and \u201cReduce\u201d on pages 67 and 69 of the newly added Other Reference #4.<\/p>\n<p>Task:<\/p>\n<p>To compute and output all equivalent sets of indistinguishable states using the \u0093Mark\u0094 method (page 67) of the new Other Reference #4 which was added today to our Course Syllabus.<\/p>\n<p>Sample DFA:<\/p>\n<p>You can use following simplification assumptions to make the required input task relatively simple:<\/p>\n<p>\u00b7 States are numbered consecutively starting from 1 and state 1 is the Initial State.<\/p>\n<p>\u00b7 Likewise input symbols are each one character long and are consecutively ordered such as 0, 1, 2, 3, \u0085 or a, b, c, d, \u2026<\/p>\n<p>\u00b7 A DFA may have one or more number of states and zero or more number of Final states.<\/p>\n<p>Under these simplifying assumptions, our sample DFA can be completely specified by the following input frame: (Note comments are NOT parts of inputs)<\/p>\n<p>\u00b7 7 \/\/ total number of states<\/p>\n<p>\u00b7 4 \/\/ total number of Final states<\/p>\n<p>\u00b7 2 \/\/ two input symbols, 0 and 1 in that order<\/p>\n<p>\u00b7 1 2 3 4 \/\/ these are four Final states. So, the other three states are non-final.<\/p>\n<p>\u00b7 1 2 \/\/ two transitions of state 0, Q0<\/p>\n<p>\u00b7 3 4 \/\/ two transitions of state 1, Q1<\/p>\n<p>\u00b7 5 5 \/\/ two transitions of state 2, Q2<\/p>\n<p>\u00b7 3 4<\/p>\n<p>\u00b7 5 5<\/p>\n<p>\u00b7 6 5<\/p>\n<p>\u00b7 6 6 \/\/ two transitions of the last state, Q6<\/p>\n<p>Illustration.<\/p>\n<p>Sample DFA: We consider the following DFA with seven states and two input symbols where Q1, Q2, Q3 and Q4 are final.<\/p>\n<p><center><a href=\"http:\/\/onlineclassesguru.com\/orders\/ordernow\"><img decoding=\"async\" src=\"https:\/\/encrypted-tbn0.gstatic.com\/images?q=tbn:ANd9GcTyj99p60XCLyLk1htB7-1neRt8-2QdnenNlQ&usqp=CAU\"target=\"_http:\/\/onlineclassesguru.com\/orders\/ordernow\"\/><\/center><p>","protected":false},"excerpt":{"rendered":"<p>Deterministic Finite State Acceptors play many important roles in computing applications such as compiler design and regular language equivalence testing (the task of determining whether or not two regular languages are indeed the same despite their different looks). And, in certain cases, it is not only convenient but critical that they employ the minimum possible&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-7959","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v17.0 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>DFSA Equivalence Checker-Write a well-structured program for checking equivalence of DFSA\u2019s-Automata - onlineclassesguru<\/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:\/\/onlineclassesguru.com\/index.php\/2020\/11\/17\/dfsa-equivalence-checker-write-a-well-structured-program-for-checking-equivalence-of-dfsas-automata\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"DFSA Equivalence Checker-Write a well-structured program for checking equivalence of DFSA\u2019s-Automata - onlineclassesguru\" \/>\n<meta property=\"og:description\" content=\"Deterministic Finite State Acceptors play many important roles in computing applications such as compiler design and regular language equivalence testing (the task of determining whether or not two regular languages are indeed the same despite their different looks). And, in certain cases, it is not only convenient but critical that they employ the minimum possible...\" \/>\n<meta property=\"og:url\" content=\"https:\/\/onlineclassesguru.com\/index.php\/2020\/11\/17\/dfsa-equivalence-checker-write-a-well-structured-program-for-checking-equivalence-of-dfsas-automata\/\" \/>\n<meta property=\"og:site_name\" content=\"onlineclassesguru\" \/>\n<meta property=\"article:published_time\" content=\"2020-11-17T15:35:29+00:00\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"admin_admin\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebSite\",\"@id\":\"https:\/\/onlineclassesguru.com\/#website\",\"url\":\"https:\/\/onlineclassesguru.com\/\",\"name\":\"onlineclassesguru\",\"description\":\"Cheap Professional coursework and reaction papers help\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/onlineclassesguru.com\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/onlineclassesguru.com\/index.php\/2020\/11\/17\/dfsa-equivalence-checker-write-a-well-structured-program-for-checking-equivalence-of-dfsas-automata\/#webpage\",\"url\":\"https:\/\/onlineclassesguru.com\/index.php\/2020\/11\/17\/dfsa-equivalence-checker-write-a-well-structured-program-for-checking-equivalence-of-dfsas-automata\/\",\"name\":\"DFSA Equivalence Checker-Write a well-structured program for checking equivalence of DFSA\\u2019s-Automata - onlineclassesguru\",\"isPartOf\":{\"@id\":\"https:\/\/onlineclassesguru.com\/#website\"},\"datePublished\":\"2020-11-17T15:35:29+00:00\",\"dateModified\":\"2020-11-17T15:35:29+00:00\",\"author\":{\"@id\":\"https:\/\/onlineclassesguru.com\/#\/schema\/person\/1831fa4d28e47b468621cf27932f5742\"},\"breadcrumb\":{\"@id\":\"https:\/\/onlineclassesguru.com\/index.php\/2020\/11\/17\/dfsa-equivalence-checker-write-a-well-structured-program-for-checking-equivalence-of-dfsas-automata\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/onlineclassesguru.com\/index.php\/2020\/11\/17\/dfsa-equivalence-checker-write-a-well-structured-program-for-checking-equivalence-of-dfsas-automata\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/onlineclassesguru.com\/index.php\/2020\/11\/17\/dfsa-equivalence-checker-write-a-well-structured-program-for-checking-equivalence-of-dfsas-automata\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/onlineclassesguru.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"DFSA Equivalence Checker-Write a well-structured program for checking equivalence of DFSA\\u2019s-Automata\"}]},{\"@type\":\"Person\",\"@id\":\"https:\/\/onlineclassesguru.com\/#\/schema\/person\/1831fa4d28e47b468621cf27932f5742\",\"name\":\"admin_admin\",\"image\":{\"@type\":\"ImageObject\",\"@id\":\"https:\/\/onlineclassesguru.com\/#personlogo\",\"inLanguage\":\"en-US\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/429c8d043f7a770af242b0031e8b9f2b?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/429c8d043f7a770af242b0031e8b9f2b?s=96&d=mm&r=g\",\"caption\":\"admin_admin\"},\"url\":\"https:\/\/onlineclassesguru.com\/index.php\/author\/admin_admin\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"DFSA Equivalence Checker-Write a well-structured program for checking equivalence of DFSA\u2019s-Automata - onlineclassesguru","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:\/\/onlineclassesguru.com\/index.php\/2020\/11\/17\/dfsa-equivalence-checker-write-a-well-structured-program-for-checking-equivalence-of-dfsas-automata\/","og_locale":"en_US","og_type":"article","og_title":"DFSA Equivalence Checker-Write a well-structured program for checking equivalence of DFSA\u2019s-Automata - onlineclassesguru","og_description":"Deterministic Finite State Acceptors play many important roles in computing applications such as compiler design and regular language equivalence testing (the task of determining whether or not two regular languages are indeed the same despite their different looks). And, in certain cases, it is not only convenient but critical that they employ the minimum possible...","og_url":"https:\/\/onlineclassesguru.com\/index.php\/2020\/11\/17\/dfsa-equivalence-checker-write-a-well-structured-program-for-checking-equivalence-of-dfsas-automata\/","og_site_name":"onlineclassesguru","article_published_time":"2020-11-17T15:35:29+00:00","twitter_card":"summary_large_image","twitter_misc":{"Written by":"admin_admin","Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebSite","@id":"https:\/\/onlineclassesguru.com\/#website","url":"https:\/\/onlineclassesguru.com\/","name":"onlineclassesguru","description":"Cheap Professional coursework and reaction papers help","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/onlineclassesguru.com\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/onlineclassesguru.com\/index.php\/2020\/11\/17\/dfsa-equivalence-checker-write-a-well-structured-program-for-checking-equivalence-of-dfsas-automata\/#webpage","url":"https:\/\/onlineclassesguru.com\/index.php\/2020\/11\/17\/dfsa-equivalence-checker-write-a-well-structured-program-for-checking-equivalence-of-dfsas-automata\/","name":"DFSA Equivalence Checker-Write a well-structured program for checking equivalence of DFSA\u2019s-Automata - onlineclassesguru","isPartOf":{"@id":"https:\/\/onlineclassesguru.com\/#website"},"datePublished":"2020-11-17T15:35:29+00:00","dateModified":"2020-11-17T15:35:29+00:00","author":{"@id":"https:\/\/onlineclassesguru.com\/#\/schema\/person\/1831fa4d28e47b468621cf27932f5742"},"breadcrumb":{"@id":"https:\/\/onlineclassesguru.com\/index.php\/2020\/11\/17\/dfsa-equivalence-checker-write-a-well-structured-program-for-checking-equivalence-of-dfsas-automata\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/onlineclassesguru.com\/index.php\/2020\/11\/17\/dfsa-equivalence-checker-write-a-well-structured-program-for-checking-equivalence-of-dfsas-automata\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/onlineclassesguru.com\/index.php\/2020\/11\/17\/dfsa-equivalence-checker-write-a-well-structured-program-for-checking-equivalence-of-dfsas-automata\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/onlineclassesguru.com\/"},{"@type":"ListItem","position":2,"name":"DFSA Equivalence Checker-Write a well-structured program for checking equivalence of DFSA\u2019s-Automata"}]},{"@type":"Person","@id":"https:\/\/onlineclassesguru.com\/#\/schema\/person\/1831fa4d28e47b468621cf27932f5742","name":"admin_admin","image":{"@type":"ImageObject","@id":"https:\/\/onlineclassesguru.com\/#personlogo","inLanguage":"en-US","url":"https:\/\/secure.gravatar.com\/avatar\/429c8d043f7a770af242b0031e8b9f2b?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/429c8d043f7a770af242b0031e8b9f2b?s=96&d=mm&r=g","caption":"admin_admin"},"url":"https:\/\/onlineclassesguru.com\/index.php\/author\/admin_admin\/"}]}},"_links":{"self":[{"href":"https:\/\/onlineclassesguru.com\/index.php\/wp-json\/wp\/v2\/posts\/7959"}],"collection":[{"href":"https:\/\/onlineclassesguru.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/onlineclassesguru.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/onlineclassesguru.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/onlineclassesguru.com\/index.php\/wp-json\/wp\/v2\/comments?post=7959"}],"version-history":[{"count":1,"href":"https:\/\/onlineclassesguru.com\/index.php\/wp-json\/wp\/v2\/posts\/7959\/revisions"}],"predecessor-version":[{"id":7960,"href":"https:\/\/onlineclassesguru.com\/index.php\/wp-json\/wp\/v2\/posts\/7959\/revisions\/7960"}],"wp:attachment":[{"href":"https:\/\/onlineclassesguru.com\/index.php\/wp-json\/wp\/v2\/media?parent=7959"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/onlineclassesguru.com\/index.php\/wp-json\/wp\/v2\/categories?post=7959"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/onlineclassesguru.com\/index.php\/wp-json\/wp\/v2\/tags?post=7959"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}