Theory Of Computation: Some Terminologies

Introduction

Let's discuss about some terminologies related to Theory of Comutation, that'll help us understanding the subject better.

Terminologies

Symbol is a single character. e.g. 0, 1, 2, a, b, x, y, etc.
Alphabet is a collection of symbols. Alphabets are also denoted by Sigma. e.g. {a, b}, {0, 1, 2}, {1, 2, x, y}, etc.
String is a sequence of symbols. e.g. abc, abcd, xy, xyz, a1b2, etc.
Language is a set of Strings.
To give an example of Language consider an Alphabet: {a, b}
We can have a set of Strings that start with a: {a, aa, ab, aab, aba, ...}
This is a language.
Now we can also have a finite set. Consider a set of Strings of length 3: {aaa, aab, abb, aba, bbb, bba, baa, bab}
This is also a language.
Cardinality is the number of elements in a set.
So for the above examples of language, cardinality is infi and 8 respectively.
Sigma Star is the set of all possible Strings of all lengths over an alphabet {0, 1}

Conclusion

Getting to know about these terminologies will surely help you a lot in grasping the more complex concepts in Theory of Computation. So see you there!