ECS 120 Lecture Notes - Lecture 3: Finite-State Machine, Regular Expression, State Diagram
31 May 2018
School
Department
Course
Professor
Week 2
Lecture 4& lecture 5
Fun facts:
1. Alan Turing Movie
a. https://en.wikipedia.org/wiki/The_Imitation_Game
b. Point was that this Turing Machines cant solve all questions
c. Super good mathematician and arguably the founder of modern day computers.
Before starting lecture understand
1. is used to show something is apart of another thing
a. aAlphabet
i. What this means is the letter a “is in” the alphabet
ii. SK
1. If S = start state
2. K = all states
3. This means that the start state S “is in” the list of all states
b.
i. This means an empty symbol,
Reject states, are all states that arent accept states.
2. Point is that these two look the same but are very different.
So far we have seen 2 ways to describe a DFSM:
1. State diagram
2. 5-tuple
3. In words (last lecture only accepts even number of zeros)
a. We will be exploring this logic more this lecture.
b. This method is called Regular expressions
Let A be defined by the language that is accepted by a DFSM.
1. What does A’ DFSM do?
a. This is all the machine that accepts all strings that arent accepted by L(A),
are accepted by the machine A’
2. Is there a FSM for A’
a. Switch all accept and reject states
Main part of the lecture
Minimizing Finite State Machines:
1. As mentioned early not all DFSM have the same number of states.
a. Assume two machines that both accept the same language R and R’, if they
accept the same language are they say diagram?
i. Not always can be different number of states and different rules,
b. LEt's find a way to test to be able to see if the rules and states can be
manipulated to show that they both are the same.
find more resources at oneclass.com
find more resources at oneclass.com
2. Isomorphic languages
a. L(M) = R
b. L(M’) = R’
c. If R = R’
d. Then L(M) = L(M’)
e. This method is used to prove that two languages are the same.
3. Indistinguishable
a. Very important concept
b. If two states do the same thing( meaning they have the same rules) they are
indistinguishable.
c. There is no way to tell the difference between the two states.
d. If two machines are indistinguishable they are the same machine.
4. So the claim is that we have two machines L(M) & L(M’)
a. If both are given the same input and both are indistinguishable then both will
accept or reject for all strings(w) in the same manner.
i. Why can't we just run strings into both machines and test if they are
regular?
1. Well then we would have to test all possible strings that could
exist in the alphabet to prove this, so we would be testing an
infinite amount of strings to prove this.
ii. So proof has to be done by claiming that they are indistinguishable
machines
b. What if one machine accepts and the other rejects for an input?
i. They are distinguishable
1. Meaning they are not the same. And the languages they accept
are not the same.
5. What is reducing states?
a. Reducing is a method that allows identical states to be merge in the same
machine.
b. Why is this a good thing?
i. Less states often means less confusion.
ii. Also if two machines are both fullly reduced, they both will have the same
states and same rules, thereffore alot easier to tell if they both accept the
same language.
c. If M and M’ both accept the same language and then are reduced, they both will
still accept the same language.
Lecture 5
Distinguishable q & q’ if w & w → q = S & w-->q’ S
1. q and q’ are two states
find more resources at oneclass.com
find more resources at oneclass.com
2. w
a. w is a string
b. That is in
c. * all possible strings that can be made from the alphabet.
3. But both q and q’ on the input of this w lead to different states. If they lead to different
states they are distinguishable.
Indistinguishable q & q’ if w & w → q = S & w-->q’ =S
1. Both go to same place.
If indistinguishable we can combine and make one state.
Remove a class form L.
Examine class with each , if goes to S or not put into classes.
Both L(M) & L(Mreduced) accept same languages.
Best way to learn this is to go to youtube and check out videos on minimization of DFSM.
https://www.youtube.com/watch?v=0XaGAkY09Wc
https://www.youtube.com/watch?v=UiXkJUTkp44
The document that ive attached is the summary provided by the professor
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Fun facts: alan turing movie, https://en. wikipedia. org/wiki/the_imitation_game, point was that this turing machines cant solve all questions, super good mathematician and arguably the founder of modern day computers. Before starting lecture understand: is used to show something is apart of another thing, what this means is the letter a is in the alphabet, aalphabet. Sk: if s = start state, k = all states, this means that the start state s is in the list of all states. Reject states, are all states that arent accept states. This means an empty symbol: point is that these two look the same but are very different. They are distinguishable: meaning they are not the same. Also if two machines are both fullly reduced, they both will have the same states and same rules, thereffore alot easier to tell if they both accept the same language.
