Language Theory Foundations - Regular Expressions

Regular Expressions (known as regex) are a means to specify possible strings within a language.

Regex Operations

Operation	Description	Symbol	Example	Regular Expression
Concatenation	Combine Strings		ab	ab
			[a-c][de]	ad ∪ ae ∪ bd ∪ be ∪ cd ∪ ce
Kleene Star Closure	Get Between Zero and Multiple	*	[ab]*	(a ∪ b)*
Disjunction			A	(a ∪ b)* ∪ A
One or More	Get at Least One	+	[ab]+	(a ∪ b)^+
Zero or One	Get One Instance or Empty	?	a?	(a ∪ λ)
One Character	Get One Character from Alphabet	.	a.a	a(a ∪ b)a for Σ={a,b}
n Times	Repeat n Times	{n}	aaaa = a^4
n or More Times	Repeat n or More Times	{n,}	a{4,}	aaaa^+
n to m Times	Repeat between n and m Times	{n, m}	a{4, 6}	aaaa ∪ aaaaa ∪ aaaaaa