CS402 FAQs

Automata Theory

FAQ's about Lectures 1 to 5

QNo1. What is the difference between the strings and the words of a language?

Whether Alphabet is an element of a set or it is a set itself ?

QNo.3 What is Null String (Λ) ?

QNo.4 What is PALINDROME ?

QNo5. What is the concept of valid and invalid alphabets ?

QNo 6. What is ALGOL ?

QNo7. What are the Sequential Operators?

between them ?

QNo 9. What is meant by equivalent FA's ?

QNo 10. What is the difference between Palindrome and Reverse function? QNo11. Define Kleene Star?

QNo12. Valid/In-Valid alphabets?

QNo13. What is Reverse of a string?

QNo14. Differentiate Kleene Star Closure and PLUS?

QNo15. Define Regular Expression?

QNo1. What is the difference between the strings and the words of a language?

A string is any combination of the letters of an alphabet where as the words of a language are the strings that are always made according to certain rules used to define that language. For example if we take Alphabet Σ = { a , b } Here a , b are the letters of this alphabet. As you can see we can make a lot of strings from these letters a and b.

a,b,aa,ab,ba,bb,aaa,aab,aba,baa,............................................................ and so on. But when we define a language over this alphabet having no a's and only odd number of b's. Then the words of this language would have only those strings that have only odd number of b's and no a's. some example words of our defined language are b , bbb , bbbbb , bbbbbbb ,...................................and so on. So we can say that all the words are strings but all the strings may not be the words of a language. So strings are any combination of letters of an alphabet and the words of a language are strings made according to some rule.

Whether Alphabet is an element of a set or it is a set itself?

An Alphabet is a set in itself. The elements of an Alphabet are called letters .

Binary Alphabet Σ = {0,1} Here 0,1 are the letters of binary alphabet. Binary Alphabet is very important because it the Alphabet used by the computer. Set of Natural Numbers N={1,2,3,4,5,.........................................} Here 1,2,3........................................... are the elements of set of Natural Numbers.

QNo.3 What is Null String (Λ) ?

The string with zero occurrences of symbols (letters) from ∑. It is 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.

QNo.4 What is PALINDROME ?

The language consisting of Λ (Null String) and the strings s defined over an Alphabet Σ such that Rev(s)=s. Some example words of this language are aa As Rev(aa) = aa aba As Rev(aba) = aba bbb As Rev(bbb) = bbb aabaa As Rev(aabaa) = aabaa bbbaaabbb As Rev( bbbaaabbb ) = bbbaaabbb It is to be noted that the words of PALINDROME are called palindromes.

QNo5. What is the concept of valid and invalid alphabets ?

While defining an alphabet of letters consisting of more than one symbols, no letter should be started with any other the letter of the same alphabet i.e. one letter should not be the prefix of another. However, a letter may be ended in the letter of same alphabet i.e. one letter may be the suffix of another. Σ= { a , b } ( Valid Alphabet)