Knowledge

Talk:Deterministic finite automaton

Source 📝

437: 427: 406: 162: 85: 818: 64: 33: 2028:(the grammar there isn't even a regular one). I guess you suggest to replace this exmaple by a simpler one; and I agree with that. What about e.g. floating point numbers, integer numbers, or identifiers in some fixed programming language, or password rules (like "at least an upper case, a lower case letter, a digit, and a punctuation char must occur")? The available images at 2102: 1961: 850:
transition for each pair of states and inputs. The definition for NFA only addresses the case of a single input leading to multiple, different states. What about the case where an input leads off to a "dummy state" that just loops back to itself on every input? If we just eliminate the dummy state
808:
The section on regular language is the best place to parse this. The * is the Kleene Star mentioned in that article. So 1* is the set { epsilon, 1, 11, 111, 1111...) The Kleene star operator over a number of the alphabet symbols such as (01)* is the set { epsilon, 01, 0101, 010101...) Essentially it
2023:
Ooops! I found the sentence "... decides whether or not online user input such as email addresses are valid", and just inserted "syntactically" to indicate that no automaton can check whether a specified mailbox actually exists at the provider site. I wasn't aware of the complexity of address rules
2050:
Identifiers in C are probably a nice example since you have a small alphabet (letters, digits, underscore). Password rules ("at least an upper case, a lower case letter, a digit, and a punctuation char must occur"), while simple to describe textually, would probably already be too big. (I think you
1461:
I've removed the "Accept and Generate Modes" section on that grounds that it's original research by a defunct user. A search through my textbooks, university library search engine and Google didn't reveal anyone else who's talking about generate modes for DFAs. Even if that section isn't original
884:
Missing paths are no big deal; the definition of what it means to run such an automaton will most likely say that if a path is missing, the automaton immediately halts (this can be simulated by adding an extra state and a new path to this state for each missing path in the original automaton). So
183: 2129:
It should be mentioned in this article that several transitions labeled with different input symbols leading from state A to state B can be combined into one transition to display the diagram in a simplified way. Technically, however, they are separate transitions, of course.
992:(NFAs). This is because, firstly any DFA is also an NFA, so an NFA can do what a DFA can do. Also, given an NFA, one can build a DFA that recognizes the same language as the NFA, although the DFA could have exponentially larger number of states than the NFA. 2077:
Isn't the description wrong? I understand the sentence to mean that each state must have a transition and the automaton must have a transition for each input symbol, but as far as I know, each state must have a transition for each input symbol.
747:
i m a student of computer science engineering and for me automata theory and formal languages is a very new subject. i m not being able to get hold of the subject properly. i cannot understand the subject. please suggest somthing.
1515:
says "A local automaton is a DFA for which all edges with the same label lead to a single vertex." I suggest adding "not necessarily complete" before "DFA". If we require the DFA to be complete as specified in
1481:
The description of classifiers claims that a classifier has "has more than two terminal states", which seems to imply that a DFA cannot have more than two terminal states. Should this be "more than two
673: 1168:
Many simple languages, including any problem that requires more than constant space to solve, cannot be recognized by a DFA. Another simpler example is the language consisting of strings of the form
2109:
The old description is ok (if read as "given a state and an input symbol, a transition on them is defined"), but apparently can be misleading; your suggestion is more clear, so I changed the text. -
1944: 931: 1407: 554:
Thanks Jaredwf Just a stupid question though - Finite State Machine says that it is related to 'computer science', while DFST points to 'Theory of computing'. Is this as it should be? Thanks!
207: 493: 1943:) has a proof that every local language is accepted by a local automaton (Proposition 2.1). Immediately before that, its definition of local automaton includes "not necessarily complete". 347: 1992:
as an application for deterministic finite automata. I am not sure if this is supposed to be an in-joke: the syntax and grammar of email addresses at least as defined by the original
515:
I have rewritten the intro and added the section "Accept and Generate modes", both of which aim to be a non-technical introduction. Is this sufficient to remove the technical flag?
1996:
is quite complex, and using DFAs (at least in the form of regular expressions) is kind of seen as an anti-pattern, at least as far as I understand it. See e.g. the discussion at
1968:
I believe you are right. Although every DFA can be made complete by adding an "error" state, completing a local DFA will destroy locality. Also, your proof looks convincing. -
264: 202: 791:
Can someone please explain the following entry in the article more. Now sure what this exactly is in relation to FSM (the article on regular language is just as perplexing).
1722: 2187: 1486:
of terminal states"? A DFA can obviously have three terminal states, but just two classes (accept and reject). This is not clear from the current wording on classifiers.
125: 1690: 135: 1575: 868:
pair of states and inputs should have exactly one transition. As I understand it, missing transitions are unacceptable for a DFA, and hence would be classes as an NFA.
1894: 1868: 1598: 2192: 2182: 1934: 1914: 1842: 1822: 1802: 1782: 1762: 1742: 1658: 1638: 1618: 1541: 732:
Done. I have at least two books that use this format, so I went ahead and made the change. If anyone disagrees, please comment here and let me know. Thanks!
2029: 2001: 1103:– These are more popular names of the automata theory concepts. Even within the articles the objects are referred as (non)deterministic finite automaton. 101: 2202: 483: 309: 2197: 2074:
According to the above definition, deterministic finite automata are always complete: they define a transition for each state and each input symbol.
952:
In the section "Advantages and Disadvantages", the example discribes the "bracket" language - i.e. properly paired brackets. This is not formally
283: 459: 148: 92: 69: 2154:
I agree that this should be explained somewhere. Unfortunately, diagram notation isn't explained at all in this article. Instead it links to
1493: 1093: 372: 2140: 2085: 755: 255: 534:
To what field of human endeavor does this relate? Could someone put an introductory sentance in English for the rest of us? Thanks! ;)
1948: 1084: 935: 1097: 450: 411: 236: 2158:
which handles the huge amount of existing variants; thus is is not that easy to find the right place to insert your information. -
1939:
I have not checked the references in this section to see how they define DFA. "Local languages and the Berry-Sethi algorithm" (at
1025:
Have added this. Also made some small changes in the wording for union/intersection/complement at the beginning of this section.
989: 328: 621: 1517: 1512: 1161: 1088: 597: 1467: 851:
and any inputs leading to it, does the diagram still represent a DFA? If not, is it an NFA? Or something else? Thanks,
293: 174: 44: 1145:
Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.
1057:
Subsequent comments should be made in a new section on the talk page. No further edits should be made to this section.
303: 217: 1355: 2163: 2114: 2037: 1973: 338: 100:
related articles on Knowledge. If you would like to participate, please visit the project page, where you can join
1497: 825: 365: 1463: 1108: 1015: 975: 759: 2144: 2089: 1030: 997: 961: 32: 829: 17: 2134: 1435:
I thought so, but the wording was not clear, so I changed it (adding "arbitrary" to indicate an unbounded
520: 2159: 2110: 2033: 1969: 1422: 1007: 737: 569: 274: 50: 1329:. Granted, it will take a large number of states (perhaps on the order of 2?) to embed the counting of 885:
long as there are never two paths on the same state/input pair, the automaton is deterministic. — Carl
436: 1489: 1444: 1342: 1070: 751: 585: 565: 516: 1104: 1026: 1011: 993: 971: 957: 2052: 2009: 458:
on Knowledge. If you would like to participate, please visit the project page, where you can join
2025: 1997: 1417:≥0) and I think it does so. This is not a regular language, and cannot be recognised by a DFA. 1325:
is limited to a specific finite number, it looks like a DFA can indeed be built for the language
800: 593: 555: 535: 442: 1695: 426: 405: 2056: 2013: 1462:
research, we should consider whether it lends undue weight to a rarely-discussed type of DFA.
193: 1663: 794:
The language of M can be described by the regular language given by this regular expression:
2167: 2148: 2118: 2093: 2060: 2041: 2017: 1977: 1952: 1546: 1501: 1471: 1448: 1426: 1418: 1346: 1127: 1112: 1074: 1034: 1019: 1001: 979: 965: 939: 915: 897: 877: 855: 836: 803: 781: 778: 763: 741: 733: 727: 682: 601: 576: 558: 548: 538: 524: 245: 97: 1440: 1338: 1066: 873: 615: 1873: 1847: 2005: 1620:
is a complete DFA in which all edges with the same label lead to a single vertex, then
1580: 1123: 319: 161: 1919: 1899: 1827: 1807: 1787: 1767: 1747: 1727: 1643: 1623: 1603: 1526: 184:
Requested articles/Applied arts and sciences/Computer science, computing, and Internet
2176: 2155: 1989: 892: 833: 589: 1136: 1048: 911: 852: 679: 573: 545: 2081:
My suggestion: "they define from each state a transition for each input symbol."
581:
Both are correct! Theory of Computation is a subdicipline of Computer Science.
572:, since theory of computation is a more exact answer. Thanks for noticing. -- 455: 817: 1940: 869: 724: 432: 956:, as stated, but "Strings whose each prefix has more or equal a's than b's" 696: 226: 1520:, then it is not true that local automata can accept all local languages. 84: 63: 777:. Other articles reference FSMs without the presumption of determinism. -- 888: 1337:'s, but it still seems possible. Or did I miss something in the text? — 1006:
Your suggestion is good. Please add it yourself. I also suggest to cite
614:
The symbols used to describe the 5-tuple are inconsistent with those in
2135:
https://www.cs.toronto.edu/~amir/teaching/csc236f15/materials/lec10.pdf
1993: 926:
It should be made clear that if a path is missing, the automaton halts
907: 1184:
I don't think that is correct. Consider the following state diagram:
720: 1409:
which has infinitely many words (indeed, exactly one of length 2
302:
Find pictures for the biographies of computer scientists (see
26: 2002:
How to validate an email address using a regular expression?
816: 1988:
The lead section mentions recognizing syntactically valid
668:{\displaystyle \langle Q,\Sigma ,\delta ,q_{0},F\rangle } 1047:
The following discussion is an archived discussion of a
970:
You are correct. It is bad language. Let me try a fix. (
1896:, so it either accepts both or rejects both. Therefore 2000:
here on Knowledge and the top answer to the question "
1010:
page for the algorithm that translates NFA into DFA. (
906:
I just added a new section to mention the difference.
1922: 1902: 1876: 1850: 1830: 1810: 1790: 1770: 1750: 1730: 1698: 1666: 1646: 1626: 1606: 1583: 1549: 1529: 1358: 1135:
The above discussion is preserved as an archive of a
624: 2030:
commons:Category:Deterministic finite state automata
864:: The description may be slightly ambiguous in that 454:, a collaborative effort to improve the coverage of 96:, a collaborative effort to improve the coverage of 846:The definition for DFA states that there should be 1928: 1908: 1888: 1862: 1836: 1816: 1796: 1776: 1756: 1736: 1716: 1684: 1652: 1632: 1612: 1592: 1569: 1535: 1401: 667: 208:Computer science articles needing expert attention 1352:The wording is intended to describe the language 809:means none, one, or more of the items repeating. 2026:Talk:Email_address#Complexity_of_email_addresses 1998:Talk:Email address#Complexity of email addresses 1518:Deterministic_finite_automaton#Formal_definition 1402:{\displaystyle \{a^{n}b^{n}:n\in \mathbf {N} \}} 985:Thank you. It looks better now. Also I suggest: 544:Doesn't everyone know automata theory?  :-) -- 1166: 348:WikiProject Computer science/Unreferenced BLPs 1513:Deterministic_finite_automaton#Local_automata 8: 1396: 1359: 828:so that it renders again. It's intended for 691:. Me too. We should make this change. Using 662: 625: 2051:need at least 1 + 4 + 6 + 4 + 1 states?) – 2032:are not too convincing for that purpose. - 1941:https://www.irif.fr/~jep/PDF/BerrySethi.pdf 1457:Removed "Accept and Generate Modes" section 265:Computer science articles without infoboxes 203:Computer science articles needing attention 30: 18:Talk:Read-only right moving Turing machines 1487: 988:DFAs are equivalent in computing power to 400: 169:Here are some tasks awaiting attention: 143: 58: 2188:High-importance Computer science articles 1921: 1901: 1875: 1849: 1829: 1809: 1789: 1769: 1749: 1729: 1697: 1665: 1645: 1625: 1605: 1582: 1550: 1548: 1528: 1523:For example, consider the local language 1391: 1376: 1366: 1357: 675:? My textbook also uses these notations. 650: 623: 402: 60: 1945:2600:1700:6EC0:35C0:D5F2:3A1:B655:C5F7 932:2600:1700:6EC0:35C0:D5F2:3A1:B655:C5F7 110:Knowledge:WikiProject Computer science 2193:WikiProject Computer science articles 2183:Start-Class Computer science articles 1094:Nondeterministic finite-state machine 113:Template:WikiProject Computer science 7: 1062:The result of the move request was: 842:Missing paths - still deterministic? 787:Regular languages in relation to FSM 448:This article is within the scope of 90:This article is within the scope of 1176:'s, followed by an equal number of 49:It is of interest to the following 1085:Deterministic finite-state machine 634: 284:Timeline of computing 2020–present 25: 2203:Mid-priority mathematics articles 2125:Simplified diagram representation 2069:Section "Complete and incomplete" 1984:Recognizing valid email addresses 1098:Nondeterministic finite automaton 824:I've just fixed up the DFA image 468:Knowledge:WikiProject Mathematics 310:Computing articles needing images 2198:Start-Class mathematics articles 2100: 1959: 1916:is not the language accepted by 1640:is not the language accepted by 1392: 990:nondeterministic finite automata 471:Template:WikiProject Mathematics 435: 425: 404: 160: 83: 62: 31: 1764:such that all edges with label 488:This article has been rated as 130:This article has been rated as 1089:Deterministic finite automaton 678:I'm in favor of this change. 602:09:36, 16 September 2009 (UTC) 1: 1978:17:10, 5 September 2020 (UTC) 1953:22:12, 4 September 2020 (UTC) 1543:consisting of all strings on 1508:Definition of local automaton 1128:20:37, 25 November 2011 (UTC) 1113:15:04, 25 November 2011 (UTC) 940:22:26, 4 September 2020 (UTC) 916:09:47, 11 November 2015 (UTC) 898:03:21, 23 December 2007 (UTC) 878:03:05, 23 December 2007 (UTC) 742:00:01, 11 December 2008 (UTC) 683:06:47, 11 November 2005 (UTC) 462:and see a list of open tasks. 364:Tag all relevant articles in 104:and see a list of open tasks. 2168:12:29, 28 October 2021 (UTC) 2149:11:40, 28 October 2021 (UTC) 2119:16:13, 24 October 2021 (UTC) 2094:09:19, 24 October 2021 (UTC) 2061:15:17, 4 November 2020 (UTC) 2042:13:03, 4 November 2020 (UTC) 2018:11:37, 4 November 2020 (UTC) 1472:18:42, 31 January 2015 (UTC) 1449:22:01, 27 January 2014 (UTC) 1427:19:38, 27 January 2014 (UTC) 1347:17:48, 27 January 2014 (UTC) 1075:15:54, 3 December 2011 (UTC) 856:15:25, 29 October 2007 (UTC) 782:02:25, 3 December 2005 (UTC) 618:. Is it better to change to 373:WikiProject Computer science 149:WikiProject Computer science 93:WikiProject Computer science 1717:{\displaystyle abc\notin A} 1502:14:16, 9 October 2019 (UTC) 1035:06:53, 18 August 2011 (UTC) 1020:11:30, 17 August 2011 (UTC) 1002:06:46, 17 August 2011 (UTC) 980:13:34, 16 August 2011 (UTC) 966:10:18, 16 August 2011 (UTC) 304:List of computer scientists 2219: 2133:See at the top of page 3: 826:Image:DFA search mommy.svg 804:20:51, 13 April 2006 (UTC) 728:14:17, 26 April 2007 (UTC) 525:18:50, 5 August 2010 (UTC) 136:project's importance scale 948:Possible error in example 837:03:57, 2 April 2007 (UTC) 764:06:23, 6 March 2010 (UTC) 487: 420: 366:Category:Computer science 142: 129: 116:Computer science articles 78: 57: 1685:{\displaystyle ccc\in A} 1172:— some finite number of 1142:Please do not modify it. 1054:Please do not modify it. 832:but may be useful here. 577:15:46, 14 May 2004 (UTC) 559:15:39, 14 May 2004 (UTC) 549:07:27, 14 May 2004 (UTC) 539:06:21, 14 May 2004 (UTC) 494:project's priority scale 368:and sub-categories with 1570:{\displaystyle {a,b,c}} 1064:Moves made, uncontested 830:string search algorithm 451:WikiProject Mathematics 1930: 1910: 1890: 1864: 1838: 1818: 1798: 1778: 1758: 1738: 1718: 1686: 1654: 1634: 1614: 1594: 1571: 1537: 1403: 1182: 928:and rejects the string 821: 669: 329:Computer science stubs 39:This article is rated 1931: 1911: 1891: 1865: 1839: 1819: 1799: 1779: 1759: 1739: 1719: 1687: 1655: 1635: 1615: 1595: 1572: 1538: 1404: 1152:DFA cannot recognize 1008:powerset construction 820: 695:conflicts with S for 670: 570:theory of computation 1920: 1900: 1874: 1848: 1828: 1808: 1788: 1768: 1748: 1728: 1696: 1664: 1644: 1624: 1604: 1581: 1577:that do not contain 1547: 1527: 1356: 622: 566:finite state machine 474:mathematics articles 147:Things you can help 1889:{\displaystyle ccc} 1863:{\displaystyle abc} 1660:. Proof: Note that 1464:Chip Wildon Forster 1926: 1906: 1886: 1860: 1834: 1814: 1794: 1774: 1754: 1734: 1714: 1682: 1650: 1630: 1610: 1593:{\displaystyle ab} 1590: 1567: 1533: 1399: 822: 665: 443:Mathematics portal 45:content assessment 1929:{\displaystyle M} 1909:{\displaystyle A} 1837:{\displaystyle q} 1817:{\displaystyle M} 1797:{\displaystyle q} 1777:{\displaystyle c} 1757:{\displaystyle M} 1737:{\displaystyle q} 1653:{\displaystyle M} 1633:{\displaystyle A} 1613:{\displaystyle M} 1536:{\displaystyle A} 1504: 1492:comment added by 896: 754:comment added by 605: 588:comment added by 508: 507: 504: 503: 500: 499: 399: 398: 395: 394: 391: 390: 387: 386: 16:(Redirected from 2210: 2160:Jochen Burghardt 2111:Jochen Burghardt 2108: 2104: 2103: 2034:Jochen Burghardt 1970:Jochen Burghardt 1967: 1963: 1962: 1935: 1933: 1932: 1927: 1915: 1913: 1912: 1907: 1895: 1893: 1892: 1887: 1869: 1867: 1866: 1861: 1843: 1841: 1840: 1835: 1823: 1821: 1820: 1815: 1803: 1801: 1800: 1795: 1783: 1781: 1780: 1775: 1763: 1761: 1760: 1755: 1744:be the state of 1743: 1741: 1740: 1735: 1723: 1721: 1720: 1715: 1691: 1689: 1688: 1683: 1659: 1657: 1656: 1651: 1639: 1637: 1636: 1631: 1619: 1617: 1616: 1611: 1599: 1597: 1596: 1591: 1576: 1574: 1573: 1568: 1566: 1542: 1540: 1539: 1534: 1408: 1406: 1405: 1400: 1395: 1381: 1380: 1371: 1370: 1144: 1056: 886: 848:one and only one 813:DFA search image 766: 674: 672: 671: 666: 655: 654: 604: 582: 476: 475: 472: 469: 466: 445: 440: 439: 429: 422: 421: 416: 408: 401: 377: 371: 246:Computer science 175:Article requests 164: 157: 156: 144: 118: 117: 114: 111: 108: 107:Computer science 98:Computer science 87: 80: 79: 74: 70:Computer science 66: 59: 42: 36: 35: 27: 21: 2218: 2217: 2213: 2212: 2211: 2209: 2208: 2207: 2173: 2172: 2127: 2101: 2099: 2071: 1990:email addresses 1986: 1960: 1958: 1918: 1917: 1898: 1897: 1872: 1871: 1846: 1845: 1826: 1825: 1806: 1805: 1786: 1785: 1766: 1765: 1746: 1745: 1726: 1725: 1694: 1693: 1662: 1661: 1642: 1641: 1622: 1621: 1602: 1601: 1579: 1578: 1545: 1544: 1525: 1524: 1510: 1494:131.174.142.107 1479: 1459: 1372: 1362: 1354: 1353: 1309: 1301: 1293: 1285: 1277: 1269: 1261: 1250: 1242: 1234: 1226: 1218: 1207: 1199: 1191: 1158: 1149: 1140: 1052: 1042: 950: 844: 815: 798: 789: 772: 749: 715:conflicts with 703:conflicts with 646: 620: 619: 616:Automata theory 612: 583: 532: 513: 473: 470: 467: 464: 463: 441: 434: 414: 383: 380: 375: 369: 357:Project-related 352: 333: 314: 288: 269: 250: 231: 212: 188: 132:High-importance 115: 112: 109: 106: 105: 73:High‑importance 72: 43:on Knowledge's 40: 23: 22: 15: 12: 11: 5: 2216: 2214: 2206: 2205: 2200: 2195: 2190: 2185: 2175: 2174: 2171: 2170: 2141:46.223.160.163 2126: 2123: 2122: 2121: 2086:46.223.160.111 2070: 2067: 2066: 2065: 2064: 2063: 2045: 2044: 2006:Stack Overflow 1985: 1982: 1981: 1980: 1925: 1905: 1885: 1882: 1879: 1859: 1856: 1853: 1833: 1824:terminates at 1813: 1793: 1773: 1753: 1733: 1713: 1710: 1707: 1704: 1701: 1681: 1678: 1675: 1672: 1669: 1649: 1629: 1609: 1589: 1586: 1565: 1562: 1559: 1556: 1553: 1532: 1509: 1506: 1478: 1475: 1458: 1455: 1454: 1453: 1452: 1451: 1430: 1429: 1398: 1394: 1390: 1387: 1384: 1379: 1375: 1369: 1365: 1361: 1319: 1318: 1315: 1307: 1299: 1291: 1283: 1275: 1267: 1259: 1256: 1248: 1240: 1232: 1224: 1216: 1213: 1205: 1197: 1189: 1162:article states 1157: 1150: 1148: 1147: 1137:requested move 1131: 1130: 1105:Ashutosh Gupta 1101: 1100: 1091: 1080: 1078: 1060: 1059: 1049:requested move 1043: 1041: 1040:Requested move 1038: 1027:Raghunandan ma 1012:Ashutosh Gupta 994:Raghunandan ma 972:Ashutosh Gupta 958:Raghunandan ma 949: 946: 945: 944: 943: 942: 921: 920: 919: 918: 901: 900: 881: 880: 843: 840: 814: 811: 796: 788: 785: 771: 770:Merge proposal 768: 756:115.248.12.253 745: 744: 730: 664: 661: 658: 653: 649: 645: 642: 639: 636: 633: 630: 627: 611: 608: 607: 606: 579: 564:I changed the 552: 551: 531: 528: 512: 511:Technical flag 509: 506: 505: 502: 501: 498: 497: 486: 480: 479: 477: 460:the discussion 447: 446: 430: 418: 417: 409: 397: 396: 393: 392: 389: 388: 385: 384: 382: 381: 379: 378: 361: 353: 351: 350: 344: 334: 332: 331: 325: 315: 313: 312: 307: 299: 289: 287: 286: 280: 270: 268: 267: 261: 251: 249: 248: 242: 232: 230: 229: 223: 213: 211: 210: 205: 199: 189: 187: 186: 180: 168: 166: 165: 153: 152: 140: 139: 128: 122: 121: 119: 102:the discussion 88: 76: 75: 67: 55: 54: 48: 37: 24: 14: 13: 10: 9: 6: 4: 3: 2: 2215: 2204: 2201: 2199: 2196: 2194: 2191: 2189: 2186: 2184: 2181: 2180: 2178: 2169: 2165: 2161: 2157: 2156:State diagram 2153: 2152: 2151: 2150: 2146: 2142: 2137: 2136: 2131: 2124: 2120: 2116: 2112: 2107: 2098: 2097: 2096: 2095: 2091: 2087: 2082: 2079: 2075: 2068: 2062: 2058: 2054: 2049: 2048: 2047: 2046: 2043: 2039: 2035: 2031: 2027: 2022: 2021: 2020: 2019: 2015: 2011: 2007: 2003: 1999: 1995: 1991: 1983: 1979: 1975: 1971: 1966: 1957: 1956: 1955: 1954: 1950: 1946: 1942: 1937: 1923: 1903: 1883: 1880: 1877: 1857: 1854: 1851: 1831: 1811: 1791: 1771: 1751: 1731: 1711: 1708: 1705: 1702: 1699: 1679: 1676: 1673: 1670: 1667: 1647: 1627: 1607: 1587: 1584: 1563: 1560: 1557: 1554: 1551: 1530: 1521: 1519: 1514: 1507: 1505: 1503: 1499: 1495: 1491: 1485: 1476: 1474: 1473: 1469: 1465: 1456: 1450: 1446: 1442: 1438: 1434: 1433: 1432: 1431: 1428: 1424: 1420: 1416: 1412: 1388: 1385: 1382: 1377: 1373: 1367: 1363: 1351: 1350: 1349: 1348: 1344: 1340: 1336: 1332: 1328: 1324: 1317:And so forth. 1316: 1313: 1305: 1297: 1289: 1281: 1273: 1265: 1257: 1254: 1246: 1238: 1230: 1222: 1214: 1211: 1203: 1195: 1187: 1186: 1185: 1181: 1179: 1175: 1171: 1165: 1163: 1155: 1151: 1146: 1143: 1138: 1133: 1132: 1129: 1126: 1125: 1120: 1117: 1116: 1115: 1114: 1110: 1106: 1099: 1095: 1092: 1090: 1086: 1083: 1082: 1081: 1077: 1076: 1072: 1068: 1065: 1058: 1055: 1050: 1045: 1044: 1039: 1037: 1036: 1032: 1028: 1023: 1021: 1017: 1013: 1009: 1004: 1003: 999: 995: 991: 986: 983: 981: 977: 973: 968: 967: 963: 959: 955: 947: 941: 937: 933: 929: 925: 924: 923: 922: 917: 913: 909: 905: 904: 903: 902: 899: 894: 890: 883: 882: 879: 875: 871: 867: 863: 860: 859: 858: 857: 854: 849: 841: 839: 838: 835: 831: 827: 819: 812: 810: 806: 805: 802: 795: 792: 786: 784: 783: 780: 776: 769: 767: 765: 761: 757: 753: 743: 739: 735: 731: 729: 726: 722: 718: 714: 710: 706: 702: 698: 694: 690: 687: 686: 685: 684: 681: 676: 659: 656: 651: 647: 643: 640: 637: 631: 628: 617: 609: 603: 599: 595: 591: 587: 580: 578: 575: 571: 567: 563: 562: 561: 560: 557: 556:Mark Richards 550: 547: 543: 542: 541: 540: 537: 536:Mark Richards 529: 527: 526: 522: 518: 510: 495: 491: 485: 482: 481: 478: 461: 457: 453: 452: 444: 438: 433: 431: 428: 424: 423: 419: 413: 410: 407: 403: 374: 367: 363: 362: 360: 358: 354: 349: 346: 345: 343: 341: 340: 335: 330: 327: 326: 324: 322: 321: 316: 311: 308: 305: 301: 300: 298: 296: 295: 290: 285: 282: 281: 279: 277: 276: 271: 266: 263: 262: 260: 258: 257: 252: 247: 244: 243: 241: 239: 238: 233: 228: 225: 224: 222: 220: 219: 214: 209: 206: 204: 201: 200: 198: 196: 195: 190: 185: 182: 181: 179: 177: 176: 171: 170: 167: 163: 159: 158: 155: 154: 150: 146: 145: 141: 137: 133: 127: 124: 123: 120: 103: 99: 95: 94: 89: 86: 82: 81: 77: 71: 68: 65: 61: 56: 52: 46: 38: 34: 29: 28: 19: 2138: 2132: 2128: 2105: 2083: 2080: 2076: 2072: 1987: 1964: 1938: 1522: 1511: 1488:— Preceding 1483: 1480: 1460: 1436: 1414: 1410: 1334: 1330: 1326: 1322: 1320: 1311: 1303: 1295: 1287: 1279: 1271: 1263: 1252: 1244: 1236: 1228: 1220: 1209: 1201: 1193: 1183: 1177: 1173: 1169: 1167: 1159: 1153: 1141: 1134: 1122: 1118: 1102: 1079: 1063: 1061: 1053: 1046: 1024: 1005: 987: 984: 969: 953: 951: 927: 865: 861: 847: 845: 823: 807: 799: 797:1*(01*01*)* 793: 790: 774: 773: 746: 716: 712: 708: 704: 700: 692: 688: 677: 613: 553: 533: 514: 490:Mid-priority 489: 449: 415:Mid‑priority 356: 355: 339:Unreferenced 337: 336: 318: 317: 292: 291: 273: 272: 254: 253: 235: 234: 216: 215: 192: 191: 173: 172: 131: 91: 51:WikiProjects 1844:with input 1477:Classifiers 1419:Deltahedron 1321:As long as 779:Ancheta Wis 750:—Preceding 734:ThomasOwens 584:—Preceding 530:What field? 465:Mathematics 456:mathematics 412:Mathematics 41:Start-class 2177:Categories 2139:Sicro --- 2084:Sicro --- 1441:Loadmaster 1413:for every 1339:Loadmaster 1121:per nom. — 1067:Mike Cline 862:Ambigiuous 709:Autamaton 697:semigroup 517:Ounsworth 227:Computing 1784:lead to 1490:unsigned 834:Dcoetzee 752:unsigned 711:. Using 699:. Using 598:contribs 590:Ben 1220 586:unsigned 568:to say 275:Maintain 218:Copyedit 2053:Tea2min 2010:Tea2min 1994:RFC 822 1804:. Then 1484:classes 1333:'s and 1119:Support 853:Maghnus 680:Pkirlin 610:symbols 574:jaredwf 546:jaredwf 492:on the 256:Infobox 194:Cleanup 134:on the 1724:. Let 1312:aaabbb 1164:that: 801:yusufm 775:Oppose 721:monoid 237:Expand 47:scale. 2073:: --> 2004:" on 1600:. If 1439:). — 870:Pyrre 866:every 725:linas 689:agree 320:Stubs 294:Photo 151:with: 2164:talk 2145:talk 2115:talk 2106:Done 2090:talk 2057:talk 2038:talk 2014:talk 2008:. – 1974:talk 1965:Done 1949:talk 1692:but 1498:talk 1468:talk 1445:talk 1423:talk 1343:talk 1253:aabb 1160:The 1124:Ruud 1109:talk 1071:talk 1031:talk 1016:talk 998:talk 976:talk 962:talk 936:talk 912:talk 893:talk 874:talk 760:talk 738:talk 719:for 707:for 594:talk 521:talk 126:High 2024:at 1936:. 1870:or 1306:→ S 1298:→ S 1290:→ S 1282:→ S 1274:→ S 1266:→ S 1247:→ S 1239:→ S 1231:→ S 1223:→ S 1204:→ S 1196:→ S 1180:'s. 1139:. 889:CBM 484:Mid 2179:: 2166:) 2147:) 2117:) 2092:) 2059:) 2040:) 2016:) 1976:) 1951:) 1709:∉ 1677:∈ 1500:) 1470:) 1447:) 1425:) 1389:∈ 1345:) 1327:ab 1302:→ 1294:→ 1286:→ 1278:→ 1270:→ 1262:→ 1243:→ 1235:→ 1227:→ 1219:→ 1210:ab 1200:→ 1192:→ 1170:ab 1154:ab 1111:) 1096:→ 1087:→ 1073:) 1051:. 1033:) 1022:) 1018:) 1000:) 982:) 978:) 964:) 954:ab 938:) 930:. 914:) 908:Rp 891:· 876:) 762:) 740:) 723:. 663:⟩ 641:δ 635:Σ 626:⟨ 600:) 596:• 523:) 376:}} 370:{{ 2162:( 2143:( 2113:( 2088:( 2055:( 2036:( 2012:( 1972:( 1947:( 1924:M 1904:A 1884:c 1881:c 1878:c 1858:c 1855:b 1852:a 1832:q 1812:M 1792:q 1772:c 1752:M 1732:q 1712:A 1706:c 1703:b 1700:a 1680:A 1674:c 1671:c 1668:c 1648:M 1628:A 1608:M 1588:b 1585:a 1564:c 1561:, 1558:b 1555:, 1552:a 1531:A 1496:( 1466:( 1443:( 1437:n 1421:( 1415:n 1411:n 1397:} 1393:N 1386:n 1383:: 1378:n 1374:b 1368:n 1364:a 1360:{ 1341:( 1335:b 1331:a 1323:n 1314:) 1310:( 1308:9 1304:b 1300:8 1296:b 1292:7 1288:b 1284:6 1280:a 1276:3 1272:a 1268:1 1264:a 1260:0 1258:S 1255:) 1251:( 1249:5 1245:b 1241:4 1237:b 1233:3 1229:a 1225:1 1221:a 1217:0 1215:S 1212:) 1208:( 1206:2 1202:b 1198:1 1194:a 1190:0 1188:S 1178:b 1174:a 1156:? 1107:( 1069:( 1029:( 1014:( 996:( 974:( 960:( 934:( 910:( 895:) 887:( 872:( 758:( 736:( 717:M 713:M 705:A 701:A 693:S 660:F 657:, 652:0 648:q 644:, 638:, 632:, 629:Q 592:( 519:( 496:. 359:: 342:: 323:: 306:) 297:: 278:: 259:: 240:: 221:: 197:: 178:: 138:. 53:: 20:)

Index

Talk:Read-only right moving Turing machines

content assessment
WikiProjects
WikiProject icon
Computer science
WikiProject icon
WikiProject Computer science
Computer science
the discussion
High
project's importance scale
WikiProject Computer science

Article requests
Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup
Computer science articles needing attention
Computer science articles needing expert attention
Copyedit
Computing
Expand
Computer science
Infobox
Computer science articles without infoboxes
Maintain
Timeline of computing 2020–present
Photo
List of computer scientists
Computing articles needing images

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.