Browse By

Calendar

November 2024
M T W T F S S
 123
45678910
11121314151617
18192021222324
252627282930  

Introduction of Theory Of Computation Notes

by admin in Uncategorized
Languages

Languages

Definition: Any set of strings over an alphabet ∑ is called a language. The set of all strings, including the empty string over an alphabet ∑ is denoted as ∑*. Infinite languages L are denoted as L ={wϵ ∑*: w has property P }
All Possible string is called a Language. A language is accepted by DFA is called a Regular Language.

Examples:

  • (a)   L1 = {w  ϵ {0,1}* : w has an equal number of 0′ s and 1′ s}
  • (b)  L2 ={wϵ S*: w =wR: where wR is the reverse string of w}

Descriptive definition of language

The language is defined, describing the conditions imposed on its words.

Example 1

The language  L of strings of odd length, defined over Σ={a}, can be written as

L={a, aaa, aaaaa,…..}

Example 2

The language L of strings that does not start with a, defined over Σ ={a,b,c}, can be written as

L ={L, b, c, ba, bb, bc, ca, cb,  cc, …}

Example 3

The language L of strings of length 2, defined over Σ ={0,1,2}, can be written as

L={00, 01, 02,10, 11,12,20,21,22}

Example 4

The language L of strings ending in 0, defined over  Σ ={0,1}, can be written as L={0,00,10,000,010,100,110,…}

Example 5

The language EQUAL, of strings with number of a’s equal to number of b’s, defined over Σ={a,b}, can be written as

{Λ ,ab,aabb,abab,baba,abba,…}

Example 6

The language EVEN-EVEN, of strings with even number of a’s and even number of b’s, defined over Σ={a,b}, can be written as

{Λ, aa, bb, aaaa,aabb,abab, abba, baab, baba, bbaa, bbbb,…}

Example 7

The language INTEGER, of strings defined over Σ={-,0,1,2,3,4,5,6,7,8,9}, can be written as

INTEGER = {…,-2,-1,0,1,2,…}

Example 8

The language EVEN, of stings defined over Σ={-,0,1,2,3,4,5,6,7,8,9}, can be written as

EVEN = { …,-4,-2,0,2,4,…}

Example 9

The language {anbn  }, of strings defined over Σ={a,b}, as

{anbn   : n=1,2,3,…}, can be written as

{ab, aabb, aaabbb,aaaabbbb,…}

Example 10

The language {anbnan  }, of strings defined over Σ={a,b}, as {anbnan: n=1,2,3,…}, can be written as

{aba, aabbaa, aaabbbaaa,aaaabbbbaaaa,…}

Example 11

The language factorial, of strings defined over Σ={0,1,2,3,4,5,6,7,8,9} i.e.

{1,2,6,24,120,…}

Example 12

The language FACTORIAL, of strings defined over Σ={a}, as {an! : n=1,2,3,…}, can be written as {a,aa,aaaaaa,…}. It is to be noted that the language FACTORIAL can be defined over any single letter alphabet.

Example 13

The language DOUBLEFACTORIAL, of strings defined over Σ={a, b}, as {an!bn! : n=1,2,3,…}, can be written as {ab, aabb, aaaaaabbbbbb,…}

Example 14

The language SQUARE, of strings defined over Σ={a}, as {an2 : n=1,2,3,…}, can be written as

{a, aaaa, aaaaaaaaa,…}

Example 15

The language DOUBLESQUARE, of strings defined over Σ={a,b}, as

{an2 bn2 : n=1,2,3,…}, can be written as {ab, aaaabbbb, aaaaaaaaabbbbbbbbb,…}

Example 16

The language PRIME, of strings defined over Σ={a}, as

{ap : p is prime}, can be written as {aa,aaa,aaaaa,aaaaaaa,aaaaaaaaaaa…}

Palindrome

Definition: A palindrome is a string which is the same whether written or read backward or forward. The language consisting of Λ and the strings s defined over Σ  such that Rev(s)=s. It is to be denoted that the words of palindrome are called palindromes.

Example: For Σ={a,b},

palindrome ={Λ , a, b, aa, bb, aaa, aba, bab, bbb, …}

Remark

There are as many palindromes of length 2n as there are of length 2n-1. To prove the above remark, the following is to be noted:

Note: Number of strings of length ‘m’ defined over   alphabet of ‘n’ letters is nm.

Examples

  • The language of strings of length 2, defined over Σ={a,b} is L={aa, ab, ba, bb} i.e. number of strings = 22
  • The language of strings of length 3, defined over Σ={a,b} is L={aaa, aab, aba, baa, abb, bab, bba, bbb} i.e. number of strings = 23

Theory of Computation Notes

आशा करता हूँ, कि यह आर्टिकल आपको पसंद आया होगा तो सोच क्या रहे हैं अभी इसी वक्त इसे अपने दोस्तों के साथ सोशल मीडिया पर Share करें।

Thanking You………………धन्यवाद………………..शुक्रिया………………..मेहरबानी…………………..

Read More: InfoKhajana.com covered the following topics in these notes.

References –
cs.stanford.edu
Wikipedia