Basics of TOC

Symbol: These are the basic building blocks. It can be any  letter,symbol.example: a,b,c A,C, 0,1 etc.

Alphabet: Set of the symbol which is finite. example: Alphabet withSet of two symbol is{a,b} or{,0,1} etc.They are denoted by Σ

String: finite sequence of alphabet is called String.

length of String is denoted as |w|.

Example: Let us say we have two alphabet {a,b}.

1. No. of String of length 2 is 22 ​=4

2. No. of the string of length 3 is 23=8

So the formula used here is |w|n  

                   |w|= no of the alphabet, n= length of string you need. 

Language: It is a collection of string. 

let us say  Σ={a,b}

L1=set of a string of length 2 ={aa,ab,ba,bb}

L2=set of string of which starts with a ={a,ab,abba, aaba,......}

So L1 is called as finite language and L2 is an infinite language as it all depends on whether you can count the no. of strings in the language.


1.No. of the alphabet is finite.

2.No. of String in a language may be finite or may be infinite.

3. A language can be finite or infinite.


Contributor's Info