SGT

1

1 Seq(Left(Seq(a, b)), Left(Empty)) POSIX Seq(Right(a), Right(b))

2 Stars(Left(Seq(a, a)), Right(a)) POSIX Stars(Right(a), Left(Seq(a, a))) Stars(Right(a), Right(a), Right(a))

2

If we’re only using basic regular expressions, no. With extended regular expressions such as intersection, we can have an empty language for a regex such as $a\&b$.

We can use proof by induction here. [try this as an exercise?]

3

numbers = $([\mathrm{1..9}]\cdot [\mathrm{0..9}{]}^{\ast })+0$ LP = ${}^{\prime }{(}^{\prime }$ RP = ${}^{\prime }{)}^{\prime }$ ID = $[a..z{]}^{+}$ OP = ${}^{\prime }{+}^{\prime }{+}^{\prime }{-}^{\prime }{+}^{\prime }{\ast }^{\prime }$

1. LP, ID(a), OP(+), numbers(3), RP, OP(*), ID(b)
2. RP, LP, RP, OP(+), OP(+), OP(-), numbers(33)
3. Cannot be lexed.

4

[LOOK OVER THIS] If $\text{nullable}(r)$, then $1+r=r$

$$\begin{array}{rl}1+r+r\cdot r& \equiv r\cdot r\\ & \\ 1+r+r\cdot r& =(1+r)+r\cdot r\\ & =r+r\cdot r\\ & =r\cdot (1+r)\\ & =r\cdot r\end{array}$$

5

UPPER = $[A..Z]$ LOWER = $[a..z]$ DIGIT = $[\mathrm{0..9}]$ ANY = $UPPER+LOWER+DIGIT$

PASSWORD = $(ANY{)}^{\{\mathrm{8..}\}}\&(AN{Y}^{\ast }\cdot UPPER\cdot AN{Y}^{\ast })\&(AN{Y}^{\ast }\cdot LOWER\cdot AN{Y}^{\ast })\&(AN{Y}^{\ast }\cdot DIGIT\cdot AN{Y}^{\ast })$

6

$$/\ast \cdot ({\text{ALL}}^{\ast }\cdot \ast /\cdot {\text{ALL}}^{\ast })\cdot \ast /$$

7

[COPY SOLUTION]

8

Right(Right(Empty)) Seq(Right(Empty), Left(Empty)) Stars[]

9

Record regular expression allows us to mark parts of our matched string to later extract information out of the string.

10

atmostempty

$$\begin{array}{rl}a(0)& =\top \\ a(1)& =\top \\ a(c)& =\perp \\ a(r_1+r_2)& =a(r_1)\wedge a(r_2)\\ a(r_1\cdot r_2)& =\text{zeroable}(r_1)\vee \text{zeroable}(r_2)\vee (a(r_1)\wedge a(r_2))\\ a(r^{\ast })& =a(r)\end{array}$$

somechars

$$\begin{array}{rl}s(0)& =\perp \\ s(1)& =\perp \\ s(c)& =\top \\ s(r_1+r_2)& =s(r_1)\vee s(r_2)\\ s(r_1\cdot r_2)& =(\neg \text{zeroable}(r_1)\wedge s(r_2))\vee (\neg \text{zeroable}(r_1)\wedge s(r_1))\\ s(r^{\ast })& =s(r)\end{array}$$

infinitestrings

$$\begin{array}{rl}i(0)& =\perp \\ i(1)& =\perp \\ i(c)& =\perp \\ i(r_1+r_2)& =i(r_1)\vee i(r_2)\\ i(r_1\cdot r_2)& =(\neg \text{zeroable}(r_1)\wedge i(r_2))\vee (\neg \text{zeroable}(r_1)\wedge i(r_1))\\ i(r^{\ast })& =\neg a(r)\end{array}$$

11

We may encounter catastrophic backtracking with specially crafted inputs. We will have 1000 copies of some NFA / DFA, may not even have memory.