Automata

• Non-deterministic finite automata has a set of states that can be moved between according to the rules, a starting state, and accepting/final states

  
• Transitions in automata are written as a relation (list) of form (state, transition, state)

  
• An automata run is essentially the word formed by tracking the transitions from the start to an accepting state
• An automaton accepts a word iff there is a way to generate it in a run
• Automata can describe regular languages only
• The reverse of a language is also regular
• Deterministic automata = forced choices in moves
• non-deterministic automata = relations, deterministic automata = functions (only one path from each state)
• BOTH types of automata describe the same languages
• Powerset construction: 1. Get powerset of all states (all possible set options) 2. The sets become the states 3. New final states = any state set that contains a final state

  
• If a language is regular, the "language" of all the words in the alphabet that aren't in the language (its compliment) is ALSO regular. (proof - just flipping which states are rejecting/accepting in an automaton)

  
• Union (U), intersection (^) and interweaving 2 regular languages results in another regular language
• Lc = E* \ L (all words with alphabet that do not intersect (are not part of) L)
• Concatenation = L1 ◦ L2 := {uw | u ∈ L1 ∧ w ∈ L2} (take any from set1 and mash together with item from set2 in all variations)
• The empty strings/sets + terminal symbols are regular expressions. Combinations of: OR (union), concatenation and Kleene star are regular when built up from the base regulars

  
• A language is regular iff there is a regular expression denoted by it
• To get a left linear grammar from an automata, switch the start and end states, flip the arrows and work through as normal

  
• To model intersection of automata, get cart. prod. of states, and look for path combos that are valid (final state(s) = both final states originally)