Language Theory Foundations - Regular Expressions - Revision history

Brodriguez: Create some regex examples

2019-09-25T18:34:56Z

Create some regex examples

← Older revision		Revision as of 18:34, 25 September 2019
Line 99:		Line 99:
	12.5) = u(vu)*		12.5) = u(vu)*
	12.6) = (uv)u*		12.6) = (uv)u*


			== Regex Examples ==

			Ex: Let's define the set of strings over {a, b, c} with length of 3 or more.
			[abc]{3,}

			Ex: Let's define the set of strings over {a, b}, with at least one instance of "aa" and length 2 or more.
			[ab]aa[ab]

			Ex: Let's define the set of strings over {a, b}, with at least two instances of "aa".
			[ab]aa[ab]aa[ab*]

Brodriguez: Correct identity list format

2019-09-25T18:27:05Z

Correct identity list format

← Older revision		Revision as of 18:27, 25 September 2019
Line 82:		Line 82:
	Given arbitrary strings u, v, and w, we can define the following identities:		Given arbitrary strings u, v, and w, we can define the following identities:

	1) ∅u = u∅ = ∅		1) ∅u = u∅ = ∅
	2) λu = uλ = u		2) λu = uλ = u
	3) ∅ = λ		3) ∅ = λ
	4) λ* = λ		4) λ* = λ
	5) (u ∪ v) = (v ∪ u)		5) (u ∪ v) = (v ∪ u)
	6) (u ∪ ) = u		6) (u ∪ ) = u
	7) (u ∪ u) = u		7) (u ∪ u) = u
	8) u* = (u)		8) u* = (u)
	9) u(v ∪ w) = (uv ∪ uw)		9) u(v ∪ w) = (uv ∪ uw)
	10) (u ∪ v)w = (uw ∪ vw)		10) (u ∪ v)w = (uw ∪ vw)
	11) (uv)u = u(vu)		11) (uv)u = u(vu)
	12.1) (u ∪ v)* = (u* ∪ v)*		12.1) (u ∪ v)* = (u* ∪ v)*
	12.2) = u(u ∪ v)		12.2) = u(u ∪ v)
	12.3) = (u ∪ vu)		12.3) = (u ∪ vu)
	12.4) = (uv)*		12.4) = (uv)*
	12.5) = u(vu)*		12.5) = u(vu)*
	12.6) = (uv)u*		12.6) = (uv)u*

Brodriguez: Create regex identities section

2019-09-25T18:25:39Z

Create regex identities section

← Older revision		Revision as of 18:25, 25 September 2019
Line 71:		Line 71:
	\| aaaa ∪ aaaaa ∪ aaaaaa		\| aaaa ∪ aaaaa ∪ aaaaaa
	\|}		\|}


			== Regex Identities ==
			<pre>
			Recall that ∅ is the empty set. Which is different than an empty string.
			Empty string implies that the set has a string, just the string has no symbols in it.
			Empty set implies that the set has no elements at all, not even an empty string.
			</pre>

			Given arbitrary strings u, v, and w, we can define the following identities:

			1) ∅u = u∅ = ∅
			2) λu = uλ = u
			3) ∅ = λ
			4) λ* = λ
			5) (u ∪ v) = (v ∪ u)
			6) (u ∪ ) = u
			7) (u ∪ u) = u
			8) u* = (u)
			9) u(v ∪ w) = (uv ∪ uw)
			10) (u ∪ v)w = (uw ∪ vw)
			11) (uv)u = u(vu)
			12.1) (u ∪ v)* = (u* ∪ v)*
			12.2) = u(u ∪ v)
			12.3) = (u ∪ vu)
			12.4) = (uv)*
			12.5) = u(vu)*
			12.6) = (uv)u*

Brodriguez: Correct table columns

2019-09-25T18:08:31Z

Correct table columns

← Older revision		Revision as of 18:08, 25 September 2019
Line 18:		Line 18:
	\|-		\|-
	\|		\|
			\|
	\|		\|
	\| [a-c][de]		\| [a-c][de]

Brodriguez: Create page

2019-09-25T18:08:02Z

Create page

New page

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

== Regex Operations ==

{| class="wikitable"
|-
! 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
|
| |
| [ab]* | 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
|}