Search for tag: "dfa"

ECS 120 5a:5 corollary of Myhill-Nerode Theorem we use and its proof

From  David Doty 0 likes 177 plays 0  

ECS 120 5a:4 statement of Myhill-Nerode Theorem

From  David Doty 0 likes 254 plays 0  

ECS 120 6a:1 languages decided-recognized by TMs

From  David Doty 1 likes 368 plays 0  

ECS 120 5c:4 formal definition of TM semantics

errata: At 4:38, I incorrectly said and wrote that L,R,S correspond to +1, -1, and 0. They correspond to -1, +1, and 0, i.e., moving left (L) decrements (-1) the tape head position, and moving right…

From  David Doty 1 likes 287 plays 0  

ECS 120 5b:2 pumping lemma proof that 0n1n is not regular

From  David Doty 1 likes 286 plays 0  

ECS 120 5b:1 pumping lemma for regular languages

From  David Doty 1 likes 115 plays 0  

ECS 120 5a:4 direct proof that uu is not regular

From  David Doty 1 likes 65 plays 0  

ECS 120 5a:3 picture of previous proof

From  David Doty 1 likes 61 plays 0  

ECS 120 5a:2 direct proof that equal zero-one is not regular

From  David Doty 1 likes 84 plays 0  

ECS 120 5a:1 why we need rigor to argue that a language is not regular

From  David Doty 1 likes 238 plays 0  

ECS 120 4b:3 NFAs can simulate RRGs proof

From  David Doty 1 likes 196 plays 0  

ECS 120 4b:4 right-regular versus left-regular grammars

From  David Doty 1 likes 169 plays 0  

ECS 120 4b:2 RRGs can simulate DFAs proof

From  David Doty 1 likes 197 plays 0  

ECS 120 4b:1 RRGs can simulate DFAs example

From  David Doty 1 likes 319 plays 0  

ECS 120 4a:5 alternative choices in subset construction

From  David Doty 1 likes 188 plays 0  

ECS 120 4a:3 proof DFAs can simulate NFAs with no epsilon-transitions

From  David Doty 1 likes 237 plays 0