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.

SOME POINTS:

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

Created:
0Comment