What is DFA?

Known as Deterministic Finite Accepter. It accepts a finite set of internal states

It is a five-tuple, where:

  1. Q = Finite set of states
  2. ${\Sigma}$ = Finite set of input alphabet symbols.
  3. ${\sigma}$ = Transition function mapping: ${Q * {\Sigma} -> Q}$
  4. ${q_0 \in Q}$ = is the initial state.
  5. F ${\subset}$ ${Q}$ = set of final/accept states. Q($F \subset Q$) Has multiple final states.

What is NFA?

Known as Nondeterministic Finite Automata. It is a finite state accepter that has several options/relative paths that it can go to. It has choices to pick the best path.

It is a five-tuple, where:

  1. Q = Finite set of states
  2. ${\Sigma}$ = Finite set of input alphabet symbols (finite)
  3. ${\sigma}$ = Transition function mapping: ${Q * {\Sigma} -> Q}$
  4. ${q_0 \in Q}$ = is the initial state.
  5. F ${\subset}$ ${Q}$ = set of final/accept states. Has multiple final/accept states.
  6. ${\sigma}$ maps: Q * (${\Sigma}$ ${\cup}$ {${\lambda}$}) -> ${2^Q}$

2^Q is the powerset

What is a Regular Language?

It can be recognized by a DFA/NFA.

What is a Regular Expression?

It is a way to denote a regular language.

Is every subset of a regular language regular?

No, every subset of a regular language is not regular.

Proof: $L_1 = a^nb^m | n,m \ge 0$ is regular $L_2 = a^nb^n | n \ge 0$ is NOT regular

Therefore, $L_2 \subset L_1$

Closure Properties of Regular Languages

  1. If $L_1$ and $L_2$ are regular, then $L_1 \cup L_2$ is regular.
  2. If $L_1$ and $L_2$ are regular, then $L_1 \cap L_2$ is regular.
  3. If $L_1$ is regular, then $\bar L_1$ is regular.

Pumping Lemma for Regular Languages

It is used to prove nonregularity of regular languages.

Definition: Let L be an infinite regular language. Then there exists some positive integer m such that for any $w{\in}L$ with ${|w| >= m}$ can be decomposed into 3 parts:

If A is a regular language, then there is a number p (the pumping length) where, if s is any string in A of length at least p, then s may be divided into three pieces, s = xyz where it satisfies the three conditions:

  1. for each i >= 0, ${xy^iz \in A}$
  2. $|y| > 0$
  3. $|xy| <= p$

Context Free Grammars (CFG)

A context free grammar (CFG) ($G = (V, T, P, S)$) is a 4-tuple where:

  1. V = finite set of variables
  2. T = finite set of terminals
  3. P = finite set of production
  4. $S{\in}V$ is the start symbol

In context-free grammar G, if a string has two or more different derivations, then G is considered ambiguous.

For any context-free grammar that is unambiguous, then we can find another grammar that is unambiguous that still generates the same language.

Inherently ambiguous - language that can be generated only by ambigous grammars. Example of Inherently ambiguous: L = {$a^n b^n c^m $} $\cup$ {$a^n b^m c^m$}, where n, m >= 1 = $L_1 \cup L_2$

CFG generates CFL. You can generate CFG to a PDA.

Derivation

It is a sequence of substitutions to obtain a string. Ex: A -> 0A1 -> 00A11 -> 000A111 -> 000B111 -> 000#111

Context Free Languages

A Context-Free Language is any language that can be generated by some context-free grammar.

It is a collection of languages associated w/ context-free grammars.

Chomsky Normal Form

One of the simplified forms of grammar.

Is in the form: A -> BC A -> a

where: a = terminal A, B, C = variables

Note: B and C may not be the start variable.

IMPORTANT: Any context-free language can be generated by CFG in Chomsky Normal Form.

Greibach Normal Form

Pumping Lemma for Context Free Languages

If A is a CFL, then there is a number p (pumping length) where if s is any string in A of length >= p, then s can be divided into 5 pieces s = uvxyz which would satify the following conditions:

  1. for each i >= 0, $uv^ixy^i \in A$
  2. $|vy| > 0$
  3. $|vxy| <= p$

Push Down Automata (PDA)

It is a 7-tuple, where:

  1. Q = Finite set of states of control unit.
  2. $\sum$ = Finite set of input alphabet symbols.
  3. $\tau$ = Finite set of stack alphabet symbols.
  4. $\sigma$ = Transition function mapping: $\sigma$: $Q$ * ($\sum \cup$ {$\lambda$}) * $\tau$ -> $QF^$
  5. $q_0 \in$ Q is the initial state.
  6. $z \in \tau$ is the stack start symbol.
  7. $\tau \subseteq Q$ is the set of final states.

It is a class of machines that recognize context-free languages.

Are basically NDFA but they contain a stack.

The implementation of a stack would allow to recognize nonregular languages. The stack also has infinite memory.

PDA can be implemented in two ways:

  1. DPDA (Deterministic Pushdown Automata)
  2. NPDA (Non-deterministic Pushdown Automata)

For NPDA, it can determine which states to transition to depending if its the best one. ex: $\sigma(q_2,\lambda,g) = $ { $(q_3, c_3d_3), (q_10, c_9d_9)$ }

Says that machine in state q2, top of stack symbol g, can do one of the following moves: 1. go to state q3 and replace g by c3d3 OR 2. it goes to state q10 and replaces g by c9d9.

A language is context free iff some pushdown automaton recognizes it.

If pushdown automaton recognizes some language, then it is context free.

Turing Machine

It is a seven-tuple, where:

  1. Q = Finite set of states
  2. $\tau = $ Finite set of tape symbols
  3. $\sum = $ a subset of $\tau$, not including B, in the set of input symbols
  4. $\sigma$ = nexy move is the mapping: $Q * \tau$ -> $Q * \tau$ * {$L, R$}
  5. $q_0 \in Q$ is the initial state
  6. $F \subseteq Q$ is the set of final states
  7. $B$ is the blank symbol

A recurively enumerable language is recognized by a Turing Machine.

NOTE: A recursive language is accepted by a Turing Machine that will halt.