SGT

1. They use finite automata to compute the result of the regex.

   Abstract

   They create DFA / NFA, then usually perform depth first search.

2. Regular Language

   A regular language is any language that can be representeed by a regular expression. A language $L$ is regular if $L=\text{Language\_of}(R)$ for some regular expression $R$.

   Link to original

   or represented by a DFA
3. You can represent any set of strings as a sequence of characters as a regex.

   Tip

   You can concatenate any set of strings to form regex.

4. $1+a+b+c+aa+((b+c)\cdot (a+b+c))+((a+b+c)\cdot (a+b+c)\cdot (a+b+c)\cdot (a+b+c{)}^{\ast })$
5. $a^{\ast }b{b}^{\ast }$

graph LR;
	start-->A;
	A(( ))-->|a|B;
	B(( ))-->|a,b|B;
	B-->|c|C((( )));

7. s \in \Sigma^* \\ \\ B(\Sigma, Q, Qs, F, P) \\ \rho(q,c,q'): \text{Boolean} \\ \\ \hat \rho (qs, []) &= qs \\ \hat \rho (qs, c::s) &= \hat \rho \begin{pmatrix} \bigcup_{q \in qs} \{ q' | p(q,c,q') \}, s \end{pmatrix} \text{ (breadth first search)} \\ &= \bigcup_{q \in qs} \hat \rho (\{ q' | \rho(q,c,q') \}, s) \text{ (depth first search)} \end{aligned}$$
8. Begin by making sure the finite automaton is complete:

graph LR;
	start; q0((q0)); q1(((q1)));

	start-->q0;
	q0-->|a|q1;
	q1-->|b|q1;

Now, flip accepting and non accepting states.

graph LR;
	q0(((q0)));
	q1((q1));
	q2(((q2)));

	start-->q0;
	q0-->|a|q1;
	q1-->|b|q1;
	q0-->q2;
	q1-->q2;
	q2-->|a,b|q2;

9. DFA:

graph LR;
	start; q0((q0)); q1((q1)); q2(((q2)));

	start-->q0;
	q0-->|b|q0;
	q0-->|a|q1;
	q1-->|b|q0;
	q1-->|a|q2;
	q2-->|a|q2;
	q2-->|b|q0;

10

Mark all pairs that are accepting and non-accepting (brz algorithm)

Example: we look at the pair 3,2, if we try 0, we end up at 3,4, one accept/reject 3,1, if we try 0, we end up both at 4, two accept, so don’t mark

We merge the states resulting in:

graph LR;
	start;
	a((2,0));
	b((3,1));
	c(((4)));

	start-->a;
	a-->|1|a;
	a-->|0|b;
	b-->|1|a;
	b-->|0|c;
	c-->|0,1|c;

11

$$\begin{array}{rl}{Q}_0& =Q_{0}b+Q_{1}b+Q_{2}b+1\\ Q_1& =Q_{0}a\\ Q_2& =Q_{1}a+Q_{2}b\end{array}$$

Sub $Q_1$ into other equations.

$$\begin{array}{rl}{Q}_0& =Q_{0}b+Q_{0}ab+Q_{2}b+1\\ Q_1& =Q_{0}a\\ Q_2& =Q_{0}aa+Q_{2}b\end{array}$$

Arden’s lemma

$$\begin{array}{rl}{Q}_2& =Q_{0}aa(a{)}^{\ast }\end{array}$$

Sub $Q_2$ back in and Arden’s lemma

$$\begin{array}{rl}{Q}_0& =Q_{0}b+Q_{0}ab+Q_{0}aa(a{)}^{\ast }b+1\\ & =Q_0(b+ab+aa{a}^{\ast }b)+1\\ & =(b+ab+aa{a}^{\ast }b{)}^{\ast }\\ Q_1& =(b+ab+aa{a}^{\ast }b{)}^{\ast }a\end{array}$$

$Q_0$ and $Q_1$ are accepting states hence we find $Q_0+Q_1$.

$$\begin{array}{rl}{Q}_0+Q_1& =(b+ab+aa{a}^{\ast }b{)}^{\ast }\cdot (1+a)\end{array}$$

12

$2^n$

13

Some regular expressions are exponential in length (even after minimisation) when building the actual autonoma.

14

Base Case Prove for $0,1,c$

Show equivalence between known rules for nullable for these 3 cases, and check the RHS $[]\in L(r)$.

Recursive Case Prove for sequence, alternate, star.

[proofs 1 video explains this]