7/18/22 FSA's and Regular Expressions

Homework:

Class Notes:

• FSA = Finite State Automaton

• Unique model of mathematics

• Uses shapes and lines to create a diagram

• 4 main conceptual points:

1. 1 initial state

2. finite # of states

3. transitions will change the active state

4. at least one final state

• If final state is reached, then the FSA accepts the data

• Diagram of FSA

• Circles → states of the FSA

• Initial state → arrow facing towards it vertically

• Final state → double circle

• Transitions → lines between the circles

• Rules of Regular Expressions

• An empty/null string is considered a regular expression

• If ‘a’ is within the given input, then it is considered a regular expression

• If ‘a’ and ‘b’ are both regular expressions:

• Concatenation: ab

• Union a|b

• Closure: a*

• Parentheses can be used to create sub groups

• Order of operations: * > Concatenation > Union