## Theory of computing, part 3
- Grid of pairs of state
## We are left with- We are left with
- {1, 2} given
*a*{4, 4} - given
*b*{2, 1} - {2, 3} given
*a*{4, 4} - given
*b*{1, 2} - {1, 3} given
*a*{4, 4} - given
*b*{2, 2} - These do not lead to pairs we know to be distinguishable, and are therefore indistinguishable!
- Remaining pairs
## States 1, 2, and 3 are all indistinguishable, thus the minimal DFA will have three states:- States 1, 2, and 3 are all indistinguishable, thus the minimal DFA will have three states:
- {0} {1, 2, 3} {4}
- Since originally T(0,
*a*) = 3 and T(0,*b*) = 1, the new transitions are T(0,*a*) = T(0,*b*) = {1,2,3} - Similarly,
- T({1,2,3},
*a*) = 4 and T({1,2,3},*b*) = {1,2,3} - Finally, as before,
- T(4,
*a*) = 4 and T(4,*b*) = 4
- Construct minimal DFA
## The resulting DFA is much simpler:- The resulting DFA is much simpler:
*a*
*a,b*
*a,b*
*b*
**0**
**1, 2, 3**
**4**
- This recognises regular expressions of the form,
*(a + b) b* a (a + b)** - This is the simplest DFA which will recognise this language!
- Resulting minimal DFA
## We now have many equivalent ways of representing regular languages: DFA’s, NFA’s, regular expressions and regular grammars.- We now have many equivalent ways of representing regular languages: DFA’s, NFA’s, regular expressions and regular grammars.
- We can also now simply(?!) move between these various representations.
- We’ll see next lecture that the automata representation leads to a simple way of recognising some languages which are not regular.
- We’ll also begin to consider more powerful language types and correspondingly more powerful computing models!
- conclusions
## M = (Q, Σ, δ, q0, F)- M = (Q, Σ, δ, q0, F)
- Q = states a finite set
- Σ = alphabet a finite set
- δ = transition function a total function in Q Σ Q
- q0 = initial/starting state q0 Q
- F = final states F Q
- Formal definition
Directory: Courses -> g-ai04Courses -> Religion 243-rc1 Dr. Robert M. Fowler Jesus and the Gospels Department of Religion Courses -> Aaa style Citation Guide: Short Version Courses -> Short Paper #1 due: Tuesday, 4/26, 1: 30 p m. Reminder: Over the course of the quarter, you are required to write 3 out of 4 Courses -> The Argumentative Essay: Persuade Your Audience— Don’t Fight With Them! Goals Courses -> Guide to Presenting, Preserving, and Gathering the Past on the Web Courses -> Français II mme Gyllenborg Affton High School 2013-2014 Courses -> Lauri hellström content Chapter 1 g-ai04 -> Biochemistry, computing in biology g-ai04 -> Theoretical background Biochemistry/molecular biology g-ai04 -> Theory of computing, part 1 Download 31.07 Kb. Share with your friends: |