A = (Q, $\Sigma$, $\delta$, q$_0$, F)
$\hat\delta$(q$_0$, w) returns the final state after w has been processed if the starting state is q$_0$
L(A) = {w | $\hat\delta$(q$_0$, w) is in F}
This means that the language of a given deterministic Finite Automaton is given by all the words in the language
A matrix of values which are the destination state after the transition. The first row (header row) is the transition symbol, the first column is the current state.
Two approaches:
contains some $\epsilon$ transitions that allow transition to the next state without consuming any input symbol
ECLOSE(q) returns the set of states that can be travelled to from q via $\epsilon$'s. Always includes q even if there is no $\epsilon$.
note about transition states: the procedure dictates that you must find the destination states after the transition, AND the ECLOSE of that set of states. Need an example here
$L^* = \bigcup_{i = 0}^{\infty}L^i$
suppose E, F are regular expressions
Basis:
(For any action, a, defined by the transition table (or state diagram))
For a transition from a state to itself: $a + \epsilon$
For a transition from a state to another state: $a$
Induction:
$R_{ij}^{(k)} = R_{ij}^{(k-1)} ~+~~ R_{ik}^{(k-1)}(R_{kk}^{(k-1)^*})R_{kj}^{(k-1)}$
Following is a list of symbolic components to be used in the process of converting regular expressions to $\epsilon$-NFA. Following this operation, one can convert from the $\epsilon$-NFA to DFA using the approach noted in an earlier section
Regular languages have at least 4 different descriptions that represent them:
Used to prove that a language is *not* regular (by contradiction). The pumping lemma states:
There exists $n$ s.t. for every string $w$ in L s.t. $\vert w \vert \ge n$ we can break $w$ into 3 strings, $w = xyz$, such that:
Basis: if p is an accepting state and q is a non-accepting state, then the pair {p, q} is distinguishable (not equivalent)
Induction: if the same input string reaches two (already known) distinguishable states, then the originating two states are distinguishable. Used in the "table filling method"
Steps:
Larger class of languages (of which regular is a subset) called "context free". Consists of grammatical rules with the following basic components:
E $\rightarrow$ I
E $\rightarrow$ E + E
I $\rightarrow$ a
etc...
In order to avoid ambiguous grammars, that are usually a result of precedence problems, introduce new variables:
Example of unambiguous grammar:
PDA's can represent context free grammars, and vice-versa
A, B / C
Example: 1, 1 / 10. If the input is 1, and 1 is at the top of the stack, then replace 1 with 10. In other words, push 0 onto the stack.
Example: 1, 0 / $\epsilon$. If the input is 1, and 0 is at the top of the stack, then replace 0 with $\epsilon$. In other words, just pop 0 off the stack.
Consists of three steps:
See March 18 notes and week 07 slides pg 4. Basically go through all combinations of rules and 'exercise' the epsilons. Below is an example.
Similar to the pumping lemma for Regular Languages, this is used to prove that a particular language is *not* context-free. The form is just a little different
Example: $q_00011 \vdash Xq_1011$ This has the TM initially in state $q_0$ with a 0 ready to be consumed from the tape. The 0 is consumed and the head moves to the right on the tape after replacing that 0 with an X, and the state transitions to $q_1$.
$(q_1, X, R)$ - this function transitions to state $q_1%, replaces the input symbol with an X, and moves the head to the right on the tape
Given a description of an arbitrary computer program, decide whether the program finishes running or continues to run forever
This is an example of an undecidable problem.
Undecidable: a decision problem where it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer