Skip to main content

Posts

Showing posts with the label Automata

Kleene Star Closure , Kleen Plus Operation and Recursive definition of languages

Kleene Star Closure
Given Σ, then the Kleene Star Closure of the alphabet Σ, denoted by Σ * , is the collection of all strings defined over Σ, including Λ.
It is to be noted that Kleene Star Closure can be defined over any set of strings.
Examples

If Σ = {x}
Then Σ * = {Λ, x, xx, xxx, xxxx, ....}
If Σ = {0,1}
Then Σ * = {Λ, 0, 1, 00, 01, 10, 11, ....}
If Σ = {aaB, c}
Then Σ * = {Λ, aaB, c, aaBaaB, aaBc, caaB, cc, ....}
Note
Languages generated by Kleene Star Closure of set of strings, are infinite languages. (By infinite language, it is supposed that the language contains infinite many words, each of finite length).

Kleen PLUS Operation ( + )
Kleen Plus Operation is same as Kleene Star Closure except that it does not generate Λ (null string), automatically.
Example

If Σ = {0,1}
Then Σ + = {0, 1, 00, 01, 10, 11, ....}
If Σ = {aab, c}
Then Σ + = {aab, c, aabaab, aabc, caab, cc, ....}
Remark
It is to be noted that Kleene Star can also be operated on any string i.e. a * can be considered to …

Reverse of a String and Defining Languages and PALINDROME

Reverse of a String
Definition : The reverse of a string s denoted by Rev(s) or s r , 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 s r = cba
Example
Σ= {B, aB, bab, d}
s=BaBbabBd
Rev(s)=dBbabaBB

Defining Languages

The languages can be defined in different ways , such as Descriptive definition, Recursive definition, using Regular Expressions(RE) and using Finite Automaton(FA) etc.

Descriptive definition of language
The language is defined, describing the conditions imposed on its words.
Example
The language L of strings of odd length, defined over Σ={a}, can be written as
L={a, aaa, aaaaa,.....}
Example
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
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
The language L of strings ending in 0, defined…

Introduction to Theory of Computation(Automata)

Summary
Introduction to the course title, Formal and In-formal languages, Alphabets, Strings, Null string, Words, Validand In-valid alphabets, length of a string, Reverse of a string, Defining languages, Descriptive definition of languages, EQUAL, EVEN-EVEN, INTEGER, EVEN, { a n b n }, { a n b n a n }, factorial, FACTORIAL, DOUBLEFACTORIAL, SQUARE, DOUBLESQUARE, PRIME, PALINDROME.

What does automata mean?
Definition : It is the plural of automaton, and it means “something that works automatically”
Introduction to languages
There are two types of languages
                    1) Formal Languages (Syntactic languages)                    2) Informal Languages (Semantic languages)

Alphabets
Definition : A finite non-empty set of symbols (called letters), is called an alphabet. It is denoted by Σ ( Greek letter sigma).
Example
Σ = {a,b}
Σ = {0,1} (important as this is the language which the computer understands.)
Σ = {i,j,k}
Note
Certain version of language ALGOL has 113 letters.
Σ (alphabet) i…