Want to contribute? Click here to suggest edits or additions.

cont.

Let’s black box a set of states to a single path.

Define the complexity of the FSA as the # of states. If we keep reducing the states, we’ll eventually get to the simplest form.

Only one start state and only one accept state. This can always be done. If multiple starts, just put another state and take epsilons to the starts. Similarly from the finals to a single Final state.

Lets attempt to make it simpler (as defined above).

Defn: A genralised path b/w states is one that accepts a Regex instead of just a character.

Hence we are building a “Generalised” FSA, where δ is not over Σ, but rather over 𝒫(Σ). We also define a ∅ path(empty connection), which takes from q1 to q2 when it reads nothing.

Suppose

Then, to remove R_k, change the path from q_i to q_j via R_ij ∪ R_i ∘ R_k^*∘R_j

Now suppose R_i was ∅, then R’_ij will also be ∅, so its a nice theoretic help.

Hence we can keep repeating to finally get a single regex.

---

Context Free Grammars

Consider the grammer of Arithmetic over +,-,*,/

Every expression can be broken into smaller expressions. The shortest expressions are those which are numbers.

Hence

E → E+E | E-E | E*E | E/E | (E) | N

where,

N → 0 | 1 | … | 9 | 0N | 1N | … | 9N

Hence checking if a string is E is basically a recursion to check if every part can be reduced to an expression.

(5+7) * 8

1. E → E * N
2. E → (E) * N
3. E → (N + N) * N

0^N1^N

E → 01 | 0E1

Defn

We can now define a context free gramm