Concepts

Automata

A DFA M consists of states S, an input Alphabet A an initial state <math>s^0 \in S\text{, a subset } S^{yes} </math> of accepting states, and a transition function: <math> \delta:S \times A \rightarrow S</math> that tells the DFA which state to move next.
- The set of strings that <math>M</math> accepts is collectively known as a language <math> L(M)</math>.
- <math> \delta *(s,abc) = \delta ( \delta ( \delta (s,a),b),c) </math>
- The set of all languages is uncountably infinite while the set of DFA's is only countably infinite.
- DFA-regular: for some finite alphabet <math>A</math>, a language <math> L \subseteq A* </math> is DFA-regular if there exists a DFA <math>M</math> s.t. <math>M</math> accepts a string <math>w</math> iff <math> w \in L </math>.

Closure under complement:
Closure under intersection: the intersection of two regular languages is regular.
Closure under union.

Covered on 1/26/2011. Similar notation to DFA's.

<math>M</math> accepts <math>w</math> if there exists a computation path from <math>\delta ^0</math> to <math>\delta ^{yes}</math>.
Must be able to convert a NFA of a few states to a DFA

How can we represent a NFA deterministically?
- Need to keep track of more information - more states.
- How many states does it need?
How can we determine whether a computation path exists that ends in an accepting state?
- Work backwards and record all the places you could be -- the space of states is the power set.
- A key idea is that we don't have to record all paths, just the union of all states we could be in at a given time.