What are the fundamental concepts of TOC?
TOC is usually referred to as the "Theory of Computing". Automata theory is a theoretical area of computer science and mathematics that focuses on the logic of computation about automata or basic systems.
The use of automata* helps researchers to comprehend better how computers calculate functions and resolve issues. The primary thing behind the creation of Automata Theory was the need to provide tools for describing and analyzing the dynamic behavior of discrete systems.
The term "Automaton", which is closely connected to "Automation" gave rise to the word "Automata".
The basic terminologies of the Theory of computation:
Symbol:
It is simply referred to as a character in symbols. It is an atomic unit, like a number, character, lowercase letter, etc. It can also be a term at times. The meaning of the symbols is not discussed in formal language.
For example:
Special characters a, b, c, z, 0, 1, 2, 9, +, -, *, %, etc.
Alphabet:
An alphabet is a group of characters. An alphabet is a limited collection of symbols that is not empty.
For example:
- Binary alphabets in the set = 0,1.
- A group of lowercase letters that includes ( a, b, c,.., and z).
- A collection of all-capital letters (A, B, C,..... Z).
- A set of all special characters is equal to +, &, %, etc.
String or a word:
The sequence of symbols that make up a string is limited to certain alphabets.
For example:
Aabbcabcd is a string from the alphabet "="{a, b, c, and d}" and 00011001 is a string from the binary "="{0,1}" alphabet.
If w = 0110 y = 0aa x = aabcaa z = 111.
Following that, Special string- s (also represented by X)
Concatenation-wz=0110111 is obtained.
Length-| w| = 4 | s | = 0 | x | = 6
Reversal-yR = aa0
The following are some special string sets:
E* All symbol strings from E,
E+ E* - {s}
For example:
E = {0, 1}
E* = {s, 0, 1, 00, 01, 10, 11, 000, 001,...}
E+ = {0, 1, 00, 01, 10, 11, 000, 001,.}
Length of a string:
In a string or word, it is the quantity of symbols. The symbol for it is |w|.
For example:
From the binary alphabet, w=01011001 Σ = {0,1}
|w| = 8
X= abbaddabba from binary alphabet Σ = {a,b}
|X| = 10
Language:
A language is a collection of strings drawn from a single or infinite alphabet. In other words, any subset L of E* is a language in the TOC.
The following list of special languages:
{}: The empty set/language, which has no strings.
{s}: A language with only one string, the empty string.
Example:
E = {0, 1}
L = {x | x is in E* and x contains an even number of 0’s}
E = {0, 1, 2,., 9, .}
L = {x | x is in E* and x forms a finite length real number}
= {0, 1.5, 9.326,.}
E = {a, b, c,., z, A, B,., Z}
L = {x | x is in E* and x is a Pascal reserved word}
= {Begin, End, If,...}
E = {Pascal reserved words} U { (, ), ., :, ;,...} U {Legal Pascal identifiers}
L = {x | x is in E* and x is a syntactically correct Pascal program}
E = {English words}
L = {x | x is in E*, and x is a syntactically correct English sentence}.
Closure representation of TOC:
L+: It is a set of all strings excluding Null and -strings are represented by this Positive Closure.
L*: The Kleene Closure represents the frequency of a particular alphabet for a given language, with values ranging from zero to infinite. It also contains the negative string.
L* = ΣL+
It means that language is a subset of Σ* since Σ * is a collection of all conceivable strings (typically a power set, which need not be unique here, we might say multiset) of strings. A Kleene Star is another name for this.
A Kleene Operator or Kleene Closure are other names for Kleene Star. It is used by engineers and IT specialists to create all strings that need to be included from a specified collection of letters or symbols. It belongs to the Unary operator type. All individual components of a given string must be present for the Kleene Star approach to work, but extra components or combinations of these alphabets may be used to any degree.