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