Language Theory Foundations - Languages - Revision history

Brodriguez: Add "word" definition

2019-09-28T15:13:13Z

Add "word" definition

← Older revision		Revision as of 15:13, 28 September 2019
Line 3:		Line 3:
	== Language Definition ==		== Language Definition ==
	* '''Alphabet''' ('''Σ''') - A non-empty set of characters/symbols.		* '''Alphabet''' ('''Σ''') - A non-empty set of characters/symbols.
	* '''String''' - A specific grouping of symbols from a given alphabet.		* '''String/Word''' - A specific, finite grouping of symbols from a given alphabet.
	* '''Empty String''' ('''λ''') - An "empty" grouping of symbols from a given alphabet. Aka, a grouping that excludes all potential symbols.		* '''Empty String''' ('''λ''') - An "empty" grouping of symbols from a given alphabet. Aka, a grouping that excludes all potential symbols.
	* '''Language''' ('''{λ, a, b, ...}''')- A set of strings, over the alphabet Σ.		* '''Language''' ('''{λ, a, b, ...}''')- A set of strings, over the alphabet Σ.
Line 101:		Line 101:

	=== Infinite Languages ===		=== Infinite Languages ===
	* '''Infinite Set of Strings''' ('''Σ^*''') - The ~~infinite~~ set of strings from concatenating all possible symbols together, including λ.		* '''Infinite Set of Strings''' ('''Σ^*''') - The set of all words/strings from concatenating all possible symbols together, including λ.

	Ex: If a, b ∈ Σ, then:		Ex: If a, b ∈ Σ, then:
Line 111:		Line 111:
	Σ^* = {a, b, aa, ab, bb, ba, aaa, aab, aba, abb, ...}		Σ^* = {a, b, aa, ab, bb, ba, aaa, aab, aba, abb, ...}

	* '''~~Kelene~~ Star Closure''' ('''L^*''') - All possible combinations of all string concatenations for the given language L.		* '''Keleene Star Closure''' ('''L^*''') - All possible combinations of all string concatenations for the given language L.
	** To define it another way, <code>L^* = L^0 ∪ L^1 ∪ L^2 ∪ ...</code>		** To define it another way, <code>L^* = L^0 ∪ L^1 ∪ L^2 ∪ ...</code>

Brodriguez: Add examples to * and + definitions

2019-09-25T18:07:21Z

Add examples to * and + definitions

@@ Line 81: / Line 81: @@
   L = {a^nb^n | n ≥ 0 }
   Results in {ab, aabb, aaabbb, ...}
 === Language Concatenation ===
@@ Line 93: / Line 99: @@
 Ex: Given L = {a^nb^n | n ≥ 0}:
   L * L = L^2 = {a^nb^na^mb^m | n ≥ 0, m ≥ 0}
 === Infinite Languages ===
@@ Line 107: / Line 107: @@
 * '''Σ^+''' - Similar to Σ^*, but minus the empty string (λ).
-* '''Kelene Star Closure''' ('''L^*''') - All possible combinations of all strings for the given language L.
 ** To define it another way, <code>L^* = L^0 ∪ L^1 ∪ L^2 ∪ ...</code>
 * '''Positive Closure''' ('''L^+''') - Similar to L^*, but minus the empty string (λ).

Brodriguez: Add language unions section

2019-09-25T17:27:18Z

Add language unions section

← Older revision		Revision as of 17:27, 25 September 2019
Line 83:		Line 83:

	=== Language Concatenation ===		=== Language Concatenation ===
	~~We can concatenate languages through the same syntax~~ that ~~we concatenate individual strings. Concatenation of two languages~~ is ~~equivalent to creating the set~~ defined by the concatenation of every string in language 1 onto language 2.		* '''Language Concatenation''' ('''L_1 * L_2''') - The set that is defined by the concatenation of every string in language 1 onto every string in language 2. Note that we can concatenate languages through the same syntax that we concatenate individual strings.

	To put it another way, given two languages L_1 and L_2, we can concatenate them together to get:		To put it another way, given two languages L_1 and L_2, we can concatenate them together to get:
Line 95:		Line 95:

	=== Language Union ===		=== Language Union ===
			* '''Language Union''' ('''L_1 ∪ L_2''') - The set that is a combination of all strings in Language 1 and Language 2. Note that these strings are '''not''' concatenated together.

	=== ~~Defining~~ Infinite Languages ===		Ex: Given L_1 = {a, aaa} and L_2 = {b, bbb}:
			L_1 ∪ L_2 = {a, aaa, b, bbb}

			=== Infinite Languages ===
	* '''Infinite Set of Strings''' ('''Σ^*''') - The infinite set of strings from concatenating all possible symbols together, including λ.		* '''Infinite Set of Strings''' ('''Σ^*''') - The infinite set of strings from concatenating all possible symbols together, including λ.

Brodriguez: Add better language concatenation definition

2019-09-25T17:19:55Z

Add better language concatenation definition

← Older revision		Revision as of 17:19, 25 September 2019
Line 83:		Line 83:

	=== Language Concatenation ===		=== Language Concatenation ===
	We can concatenate languages through the same syntax that we concatenate individual strings. ~~Given~~ two languages L_1 and L_2, we can concatenate them together to get:		We can concatenate languages through the same syntax that we concatenate individual strings. Concatenation of two languages is equivalent to creating the set defined by the concatenation of every string in language 1 onto language 2.

			To put it another way, given two languages L_1 and L_2, we can concatenate them together to get:
	L_1 * L_2 = { all string combinations x * y \| x ∈ L_1, y ∈ L_2 }		L_1 * L_2 = { all string combinations x * y \| x ∈ L_1, y ∈ L_2 }

Line 91:		Line 93:
	Ex: Given L = {a^nb^n \| n ≥ 0}:		Ex: Given L = {a^nb^n \| n ≥ 0}:
	L * L = L^2 = {a^nb^na^mb^m \| n ≥ 0, m ≥ 0}		L * L = L^2 = {a^nb^na^mb^m \| n ≥ 0, m ≥ 0}

			=== Language Union ===

	=== Defining Infinite Languages ===		=== Defining Infinite Languages ===

Brodriguez: Create string and language manipulation sections

2019-09-25T08:29:22Z

Create string and language manipulation sections

@@ Line 5: / Line 5: @@
 * '''String''' - A specific grouping of symbols from a given alphabet.
 * '''Empty String''' ('''λ''') - An "empty" grouping of symbols from a given alphabet. Aka, a grouping that excludes all potential symbols.
-* '''Language''' - A set of strings, over the alphabet Σ.
+* '''Language''' ('''{λ, a, b, ...}''')- A set of strings, over the alphabet Σ.
@@ Line 35: / Line 35: @@
 For the last example, note that the string does contain the requirement "aa". However, it also contains the letter "c", which is not an allowed character for the given language.

Brodriguez: Create page

2019-09-25T07:37:40Z

Create page

New page

Sets of "valid strings" and how to officially define them.

== Language Definition ==
* '''Alphabet''' ('''Σ''') - A non-empty set of characters/symbols.
* '''String''' - A specific grouping of symbols from a given alphabet.
* '''Empty String''' ('''λ''') - An "empty" grouping of symbols from a given alphabet. Aka, a grouping that excludes all potential symbols.
* '''Language''' - A set of strings, over the alphabet Σ.

Ex: Let's define a language ''L'' as:
L = { Strings comprised of ''a'''s and ''b'''s | Each string has at least one instance of "aa" }

We can then determine what strings are or are not within the language L:

{| class="wikitable"
|-
! ∈ L
! ∉ L
|-
| aa
| a
|-
| aaaa
| baba
|-
| abaa
| bb
|-
| baaba
| ababba
|-
| baababaab
| caa
|}

For the last example, note that the string does contain the requirement "aa". However, it also contains the letter "c", which is not an allowed character for the given language.