# Regular Expression
- [Regular expression](https://en.wikipedia.org/wiki/Regular_expression) on
WikiPedia
- [regular expressions 101](https://regex101.com), a tool to test and learn
regular expressions.
> [!tip] The Power of Regular Expression
>
> - Simple to construct.
> - Can express a wide range of languages.
> - Can be converted into [[fa|Finite Automaton]], which leads to efficient
> execution.
## Definition
- Regular expression $s$ denotes $L(s)$ -- a _language_ of $s$ -- a string drawn
from _alphabet_ $\Sigma$.
- **Base case:** $a \in \Sigma$, then $a$ is a regular expression and
$L(a) = \{a\}$.
- **Alternation:** $L(s|t) = L(s) \cup L(t)$.
- **Concatenation:** $L(st)$ is a string in $L(s)$ followed by a string in
$L(t)$.
- **Kleene closure:** $L(s*)$ is string in $L(s)$ concatenated zero or more
times.
> [!tip] There are hundreds of notations to help us build a regular expression,
> but all we need to construct them is one base case and three inductive rules!
## Cases
- [[c|C]]-Style comments
- `/\* [^*]* \* ( \* | [^*/] [^*]* \* )* /`
- Spaces added for readability.
- A way to construct: work out [[fa|NFA]] first, then use
- Another example given by regex101
- `(\/\*.*?\*\/?)|(([ ]+)?\/\/.*?$)`
## Regular Expression to FA
- Using Thompson's construction to convert REs to NFAs.
- Any RE has an start state and accept state, takes characters in between.
- Connecting the start state and accept state between REs using $\epsilon$
transitions.
- Convert [[nfa-to-dfa|NFAs to DFAs]] using subset construction.
```mermaid
---
title: Concatenation to NFA
---
stateDiagram-v2
direction LR
[*] --> A : epsilon
A --> B : epsilon
B --> [*] : epsilon
state A {
direction LR
[*] --> [*] : A
}
state B {
direction LR
[*] --> [*] : B
}
```
```mermaid
---
title: Alternation to NFA
---
stateDiagram-v2
direction LR
state fork <<fork>>
state join <<join>>
[*] --> fork
fork --> A : epsilon
fork --> B : epsilon
A --> join : epsilon
B --> join : epsilon
join --> [*]
state A {
direction LR
[*] --> [*] : A
}
state B {
direction LR
[*] --> [*] : B
}
```
```mermaid
---
title: Kleene Closure to NFA
---
stateDiagram-v2
direction LR
state fork <<fork>>
state join <<join>>
[*] --> fork
fork --> A : epsilon
A --> join : epsilon
join --> [*]
fork --> join : epsilon
join --> fork : epsilon
state A {
direction LR
[*] --> [*] : A
}
```