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
Basic Terminologies of Theory of Computation

Now let’s see the basic terminologies, which are important and frequently used in the Theory of Computation.

Symbol

Symbol is the smallest building block, which can be any alphabet, letter or any picture.

Example:

1, a, b, #

Alphabet

Definition: A finite non-empty set of symbols (called letters), is called an alphabet. It is denoted by ∑ ( Greek letter sigma).
Example  ∑  = {a,b}     
∑ = {a, b}
∑ = {A, B, C, D}
∑ = {0, 1, 2}
∑ = {0, 1, ….., 5]
∑ = {#, β, Δ}

Note: Certain version of language ALGOL has 113 letters. ∑ (alphabet) includes letters, digits and a variety of operators including sequential operators such as GOTO and IF

Letter

Definition: Each symbol of an alphabet may also be called a letter of the alphabet or simply a letter.   Language over an alphabet:  A set of words over an alphabet.  Languages are denoted by letter L with or without a subscript.

String

Definition: A “string” over an alphabet ∑ is a finite sequence of symbols from that alphabet, which is usually written next to one another and not separated by commas.

Example:  If ∑ = {a,b} then  a, abab, aaabb, ababababababababab 

Note that the lower case letters like x, y, a, b, u, v denote the string

Empty string or null string

Definition: Sometimes a string with no symbol at all is used, denoted by (Small Greek letter Lambda) λ or (Capital Greek letter Lambda) Λ, is called an empty string or null string.

The capital lambda will mostly be used to denote the empty string, in further discussion.

Words

Definition: Words are strings belonging to some language. Are strings containing the symbols in some alphabet. Two words are considered the same if all their characters are the same and in the same order.

Example:  If  ∑= {x} then a language L can be defined as  L={xn : n=1,2,3,…..} or L={x,xx,xxx,….} Here x,xx,… are the words of L 

Note:  All words are strings, but not all strings are words.

Valid/In-valid alphabets

While defining an alphabet, an alphabet may contain letters consisting of group of symbols for example

Σ1= {B, aB, bab, d}.

Now  consider an alphabet 

Σ2 = {B, Ba, bab, d} and a string BababB. 

This string can be tokenized in two different ways

  • (Ba), (bab), (B)
  • (B), (abab), (B)

Which shows that the second group cannot be identified as a string, defined over

Σ = {a, b}.

As when this string is scanned by the compiler (Lexical Analyzer), first symbol B is identified as a letter belonging to Σ, while for the second letter the lexical analyzer would not be able to identify, so while defining an alphabet it should be kept in mind that ambiguity should not be created.

Remarks: While defining an alphabet of letters consisting of more than one symbols, no letter should be started with the letter of the same alphabet i.e. one letter should not be the prefix of another. However, a letter may be ended in a letter of same alphabet.

Conclusion

  • Σ1= {B, aB, bab, d}
  • Σ2= {B, Ba, bab, d}

Σ1 is a valid alphabet while Σ2 is an in-valid alphabet.

Length of string

The number of symbols present in the string is known as the Length of the string. The length of the string is denoted by |w|. 

Ex: If w = 010 , |w| = 3

Possible strings are:

·         String “a” of length 1
·         String “b” of length 1
·         String “aa” of length 2
·         String “ab” of length 2
·         String “aaa” of length 3

Reverse of a String

Definition: The reverse of a string s denoted by Rev(s) or  sr,  is obtained by writing the letters of s in reverse order.
Example
If s=abc is a string defined over Σ={a,b,c}
then Rev(s) or sr = cba
Example
Σ= {B, aB, bab, d}
s=BaBbabBd
Rev(s)=dBbabaBB

Theory of Computation Notes

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

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

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

References –
cs.stanford.edu
Wikipedia