TOC Basic terms
Following are some basic terms you need to understand to learn theory of computation.
1. Symbol:
A symbol is an abstract or user-defined entity. ( it can not be defined ) like; a mark, sign, or word that indicates, signifies, or is understood as representing an idea, object, or relationship. They are used in communication to convey meaning and are an integral part of language and human cognition.
Examples:
Heart Symbol (❤️): Widely recognized as a symbol of love and affection. The heart shape is used to represent emotions and relationships.
WiFi Symbol (📶): The symbol for wireless internet connectivity, often found on electronic devices, indicating the availability of a Wi-Fi network.
So all letters, digits, characters, or any other symbol that we want to consider as a part of the language we are going to define are examples of symbols.
2. Alpbhabet.
An alphabet is a standardized set of letters or symbols used to represent the basic speech sounds of a language in a written form. Alphabets are fundamental to written language.
An alphabet is defined as a finite, non-empty set of symbols.
Conventionally we use the symbol ∑ (Greek letter capital sigma) to represent the alphabet.
Examples:
- The English alphabet consists of 26 letters, which are:
so, we can write this as:
∑ = {A, B… Z, a, b…z} is an English alphabet
- Binary alphabet.
∑ = {0,1} as binary language consists of only two symbols 0,1.
- An alphabet having 3 symbols.
3. String.
A string is a finite sequence of symbols chosen from some alphabet. (A word is a meaningful string for some language.)
Examples:
- If ∑ = {0,1}, a binary alphabet then
0, 0011, 0110, 001, 1010, 11001 ate the strings ∑.
If ∑ = {a, b, c…. z, A, B, C… Z} an English alphabet then,
Abc, pqr, name, cat, bat, piyu, is, this, college, student are some string over ∑.
Length of String:
If w is a string over ∑, then the length of w written as |w| , is the number of symbols that it contains.
Empty String:
The string of length 0 is called an empty string and is written as ε (epsilon). The length of the empty string is 0.
|ε| =0.
4. Lexicographic ordering.
Lexicographic or lexicographical ordering of strings is the same as the familiar dictionary ordering, except that shorter strings precede longer strings. That is; A list of strings w1, w2, w3…… wn over an alphabet ∑ is in lexicographic order if.
- Shorter strings appear before longer strings.
- Strings of the same length appear in their alphabetical order.
Example. 1. The lexicographic ordering of all strings over ∑={0,1} is.
{ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 100, 101, 110, 111, 0000……..}
Example 2. ∑ = {a, b}
{ε, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, aaab, aaba, aabbabaa……….}
Example 3. ∑ = {b, a}
{ε, b, a, bb, ba, ab, aa, bbb, bba,bab……………}
5. Language.
Language is a set of strings over an alphabet. i.e. A set of strings all of which are taken from some ∑*, where ∑ is a some alphabet, is called a language.
(∑* is all possible strings over ∑ including ε.)
A language is typically denoted by capital letters.
Example 1: if ∑ = {x} then,
Language L1 = {x, xxx, xxxxx, xxxxxxx…………..} i.e strings of odd length.
Example 2: L2 is a language over ∑= {a,b} where all strings starts with ‘a’}. i.e.
L2 = {a, aa, ab, aaa, aab, aba, abb, aaaa, aaab, aaba…….}.
If ∑ is an alphabet and L ⊆ ∑* then L is a language over ∑.
Example 3. ∑ = {0,1} then
∑* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 100, 101, 110, 111, 0000…} i.e is all strings over ∑.
If L1 = { Set of all strings of length 2} then L1 ⊆ ∑*.
Power of an alphabet:
If ∑ is an alphabet, we can express the set of all strings of certain length from that alphabet by using an exponential notation. i.e. power of ∑.
If ∑= {a,b} then,
∑1 = set of all strings over ∑ of length 1.
{a,b}
∑2 = set of all strings over∑ of length 2.
{aa, ab, ba, bb}
∑3 = set of all strings over ∑ of length 3.
{aaa, aab, aba, abb, baa, bab, bba, bbb}
∑k = set of all string over ∑ of length k.
∑* = ∑1 U ∑2 U ∑3 U ∑4 U ………..∑k
i.e. set of all possible strings over ∑.
A language L is a subset of ∑*. (over an alphabet ∑)
