Week 1 and 2 - Regular Expressions and Automata Flashcards
What does the regular expression E match to?
the empty word
What does the regular expression a|b match to?
the word a or the word b
What does the regular expression a* match to?
any number of the word a in a row, including 0 of them
What does the regular expression 0 match to?
nothing
What does the regular expression a+ match to?
aa*
What does the regular expression a? match to?
E | a
What is an automata?
An automata is used to check if a word matches to a regular expression. Automata are made up of states and transitions. Starting at the initial state, move along the relevant transition for the current letter until you reach the end of the word.
When does an automata reject a word?
If the word finishes on a non-accepting state or there is no transition for it to take.
What are epsilon transitions in an automata?
Transitions that can be taken without consuming the current letter. Therefore can be taken even if there are no letters remaining.
How do you remove an epsilon transition from an automata?
Duplicate all of the transitions that start from vertex V2 on to V1.
If V1 is a start state, make V2 a start state.
If v2 is an accepting state, make V1 an accepting state.
What does it mean if 2 DFAs are language equivalent?
They both accept the same langauge
What needs to be true for an automata to be minimal?
Every state is reachable
Each state much have a unique set of letters that transition to an accepting state.
How do you minimise an automata?
Put all of the accepting states in a set in one accepting state and put all the rejecting states in a set in one rejecting state.
Add the transitions from between the 2 states.
Add any transitions that would keep you in one of the new states, if you would end up making an NFA, split up the state in multiple different states.
