Table of contents 
Definition  Theory of Computation 
Basics of Formal Language Theory 
1 Crore+ students have signed up on EduRev. Have you? 
Automata theory (also known as Theory Of Computation) is a theoretical branch of Computer Science and Mathematics, which mainly deals with the logic of computation with respect to simple machines, referred to as automata.
Theory Of Computation
Some more points regarding the theory of computation:
Our view of languages is that a language is a set of strings. In turn, a string is a finite sequence of letters from some alphabet. These concepts are defined rigorously as follows.
1. Symbol: Symbol is the smallest building block, which can be any alphabet, letter or any picture.
2. Alphabets (Σ): Alphabets are set of symbols, which are always finite.
3. String: String is a finite sequence of symbols from some alphabet. String is generally denoted as w and length of a string is denoted as w.
Empty string is the string with zero occurrence of symbols, represented as ε.
Number of Strings (of length 2) that can be generated over the alphabet {a, b} 
Length of String w = 2
Number of Strings = 4
Conclusion:
For alphabet {a, b} with length n, number of strings can be generated = 2^{n}.
Note: If the number of Σ’s is represented by Σ, then number of strings of length n, possible over Σ is Σ^{n}.
4. Language: A language is a set of strings, chosen from some Σ* or we can say ‘A language is a subset of Σ* ‘. A language which can be formed over ‘ Σ ‘ can be Finite or Infinite.
5. Powers of ‘Σ‘:
Say Σ = {a,b} then
Σ^{0} = Set of all strings over Σ of length 0. {ε}
Σ^{1} = Set of all strings over Σ of length 1. {a, b}
Σ^{2} = Set of all strings over Σ of length 2. {aa, ab, ba, bb}
i.e. Σ^{2}= 4 and Similarly, Σ^{3} = 8
Σ* is a Universal Set.
Σ* = Σ^{0} U Σ^{1 }U Σ^{2} ..........
= {ε} U {a, b} U {aa, ab, ba, bb}
= ............. //infinite language
6. Convention:
Capital letters A, B, C, L, etc. with or without subscripts are normally used to denote languages.
18 videos56 docs41 tests

Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 
18 videos56 docs41 tests
