Theory of computation basic
What is Automata?
Formal definition of Finite automaton:
What is Symbol?
What is Alphabet?
What is string?
What is prefix?
What is Suffix?
What is the proper prefix/suffix?
Explain Concatenation of a string?
Explain Reverse of a string?
What is Kleene Star?
What is Kleene Closure / Plus?
What is Language?
The term "Automata" is derived from the Greek word "αὐτόματα". Which means "self acting".
Automaton, which is the plural of automata, is an abstract self-propelled computing device. Which automatically follows predetermined sequences of operations.
Such an automaton in which the number of states is finite is called finite automaton or finite state machine.
Formal definition of Finite automaton:
Automaton can be represented by a 5-tuple (Q, , , q0, F)
Q: There is a finite set of states.
There is a finite, set of symbols, which is called the alphabet of the automaton.
: There is a transition function.
q0: is the initial state from where the inputs are processed (q0 Q)
F: Q (F Q) is the final state of the state / states.
Related terminology:
Symbol:
There are basic building blocks in Symbol TOC.
Example:
a,b,0,1, pictures
Alphabet :
There is a finite set of symbols or it is a combination of symbols. This is a non-empty set. It is expressed by
Example:
={0,1} for binary
={0,1,2,3,4,5,6,7,8,9}
for decimal numbers
= {a, b, c, d....z}
For character strings in lowercase
= {A,B,C,D......Z}
For character strings in lowercase
alphabet is set
Where 'a', 'b', 'c', and 'd' are symbols.
String :
There is a finite sequence of symbols obtained from .
on alphabet set = {a, b, c, d}
'cadcab' is a valid string.
String length :
This is the number of symbols located in the string. Whom |S| is denoted by
If S='cadcab', then |S|= 6
either
If |S|= 0, it is called empty string
Which is expressed by or .
Prefix:
We also call prefix as the front end of string.
any number of the given string
from leading sybmol/symbols respectively
Another string created. ,
Example:
String :
w=0111
w=ababb
Prefix:
^,0,01,011,0111
^,a,ab,aba, abab, ababb
Suffix:
Suffix to rear or end of string
is called.
any number of the given string
Create trailing symbols/symbols
other string passed
Example:
String:
w=ababb
^,b,bb,abb,babb,ababb
^(null string) to empty string
Also called.
Proper prefix/suffix:
Such a prefix / suffix of a string that does not contain the string itself. Because while removing the suffix / prefix of a string, we also consider that string as the prefix / suffix, the string whose suffix / prefix is being removed.
Concatenation of a string :
w=a1 a2.........am
V=b1 b2...........Bn
wv =a1 a2.........an b1 b2.......bm
Reverse of a string:
We get reverse string when we write the symbols in reverse order
w=a1 a2 .....am
wR=a m a m-1.... a 2 a 1
Kleene Star:
There is an unary operator on a set of Kleene Star, *, symbols or strings. *, which gives of all possible strings including but an infinite set of all possible lengths.
Description :
* = 0 U 1 U 2 U…….
where p p of all possible lengths
is a set of strings.
Example:
If = {a, b},
*= {λ, a, b, aa, ab, ba, bb,………..}
Kleene Closure / Plus:
Set +, which gives an infinite set of all possible strings on that do not contain but on all possible lengths.
Description
+ = 1 U 2 U 3 U…….
Example :
If = { a, b } ,
+
={ a, b, aa, ab, ba, bb,…}
Language :
For some alphabets is a subset of a language *. It can be finite or infinite.
Example:
If language , of length 2
all possible strings
takes on = {a, b}
Then L = { ab, bb, ba, bb}
^ is a null string.
|^|=0 The length of a null string is 0.
^w = w^ = w = Any null string concatenating to a string w will be equal to a string in which string w is concatenating a null string. And equal to these two will be the string w that belongs to alphabet .
|a|=1 w Length will be 1.
|wa| = |w| +1 w The length of the concatenation of any one symbol in a string is the length of that string plus 1 for all strings w which are in
aR=a The reverse of a string of a single symbol is the same string.
NOTE : आप computer science से सम्बंधित content हमे इस google Form पर भेजे जो हम आपके द्वारा भेजे हुए content को वेबसाइट पर आपकी photo सहित प्रकाशित करेंगे।