Lecture#01

THEORY OF AUTOMATA
Lecture#01
Course Contents
Introduction to the course title
Formal and In-formal languages
Alphabets
Strings
Null string
Words
Valid and In-valid alphabets
length of a string
Reverse of a string
Defining languages
Course Contents
Descriptive definition of languages
EQUAL
EVEN-EVEN
INTEGER
EVEN
{an bn}
{ an bn an }
FACTORIAL
DOUBLEFACTORIAL
SQUARE
DOUBLESQUARE
PRIME
PALINDROME
The Chomsky Hierachy

A containment hierarchy of classes of formal languages
Regular
(DFA)
Contextfree
(PDA)
Contextsensitive
(LBA)
Recursivelyenumerable
(TM)
Automata
It is the plural of automaton, and it means something that works
automatically
Types of languages
1. Formal Languages (Syntactic languages)
2. Informal Languages (Semantic languages)
Alphabets
A finite non-empty set of symbols (called letters), is called an
alphabet. It is denoted by ( Greek letter sigma)
Example:
1. Binary: = {0,1}
2. All lower case letters: = {a,b,c,..z}
3. Alphanumeric: = {a-z, A-Z, 0-9}
4. DNA molecule letters: = {a,c,g,t}
Note: (alphabet) includes letters, digits and a variety of
operators
Strings
Definition
Concatenation of finite number of letters from the alphabet is
called a string.
Example
If = {a, b} then a, abab, aaabb, ababababababababab are all
strings
Note
Empty string or null string
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
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, xxx, are the words of L
Note: All words are strings, but not all strings are
words
Grammar
A grammar can be regarded as a device that enumerates
the sentences of a language - nothing more, nothing less
Alphabet,
String,
Word,
Grammar,
Language
Power of an alphabet
Let be an alphabet:
k = the set of all strings of length k
* = 0 U 1 U 2 U (All combinations of letters in )
+ = 1 U 2 U 3 U (Set of all strings in with length 1
or more)
Languages
L is a said to be a language over alphabet , only if L *
Why?
Examples:
1.
Let L be the language of all strings consisting of n 0s
followed by n 1s: L = {^,01,0011,000111,}
2.
Let L be the language of all strings of with equal number
of 0s and 1s: L = {^,01,10,0011,1100,0101,1010,1001,}
Definition: denotes the Empty language
Let L = {^}; Is L=?
NO
Finite Automata Uses

Some Applications:
Software for designing and checking the behavior of
digital circuits
Lexical analyzer of a typical compiler
Software for scanning large bodies of text (e.g., web
pages) for pattern finding
Software for verifying systems of all types that have a
finite number of states (e.g., stock market transaction,
communication/network protocol)
14
Finite Automata : Examples
action
On/Off switch
Modeling recognition of the
word then
Start state
Transition
Intermediate
state
Final state
state
Structural expressions
Grammars
Regular expressions
E.g., unix style to capture city names such as Palo Alto
CA:
[A-Z][a-z]*([ ][A-Z][a-z]*)*[ ][A-Z][A-Z]
Start with a letter
A string of other
letters (possibly
empty)
Should end w/ 2-letter state code
Other space delimited words

(part of city name)
Valid / Invalid Alphabet

While defining an alphabet, an alphabet may contain letters consisting
of group of symbols for example 1= {B, aB, bab, Ba}
Now consider an alphabet 2= {B, Ba, bab, d} and a string BababB
This string can be tokenized in two different ways
1. (Ba), (bab), (B)
2. (B), (abab), (B)
Which shows that the second group cannot be identified as a string,
defined over alphabet 2 . It makes 2 as an invalid alphabet.
Valid / Invalid Alphabet

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. Why?
Length of a String
Definition
The length of string s, denoted by |s|, is the number of
letters in the string.
Example1
={a,b} and s=ababa belongs to then |s|=5
Example2
= {B, aB, bab, d} and s=BaBbabBd belongs to then |s|
=5
Tokenizing=(B), (aB), (bab), (B), (d)
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} and s=BaBbabBd then Rev(s)=dBbabaBB
Defining a Language
The languages can be defined in different ways:
1.Descriptive definition
2.Recursive definition
3.using Regular Expressions(RE)
4.using Finite Automaton(FA) etc
Descriptive Definition of a Language

Definition: The language is defined, describing the conditions imposed
on its words.
Example1: The language L of strings of odd length, defined over ={a},
can be written as
L={a, aaa, aaaaa,..}
Example2: The language L of strings that does not start with a, defined
over ={a,b,c}, can be written as
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,}
Exercises: Descriptive Definition of a Language

Define languages L1, L2, L3, L4, L5 over alphabet ={a,b,c}
as
L1 = Language of all words with length two or less
L2 = Language of all words not ending on b
L3 = Language of all words with length odd
L4 = Language of all words not starting with a
L5 = Language of all words with letter b appearing in even
chunks
Exercises: Descriptive Definition of a Language

Define languages L1, L2, L3, L4, L5 over alphabet ={a,b}
as
L1 = Language of all words with length EVEN
L2 = Language of all words with length EVEN-EVEN
L3 = Language of all words with length EQUAL-EQUAL
L4 = Language defined as {anbn }
L5 = The language {anbnan }, of strings defined as {an bn an:
n=1,2,3,}
Define languages L1, L2, L3, L4 over alphabet ={-, 0, 1, 2, 3, 4,
5, 6, 7, 8, 9} as
L1 = Language of all words as INTEGERS

L2 = Language of all words belonging to set of natural
Kleen Star Closure

Given , then the Kleene Star Closure of the alphabet , denoted
by *, is the collection of all strings defined over , including
Note: 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)
Plus Operation (+)

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 be all possible strings defined over {a}, which
shows that a* generates , a, aa, aaa,
It may also be noted that a+ can be considered to be all possible non
empty strings defined over {a}, which shows that a+ generates a, aa,
aaa, aaaa,

Lecture#01

Uploaded by

Copyright:

Available Formats

Lecture#01

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lecture#01

Uploaded by

Copyright:

Available Formats

THEORY OF AUTOMATA

The Chomsky Hierachy

Finite Automata Uses

Finite Automata : Examples

Should end w/ 2-letter state code

Other space delimited words

Valid / Invalid Alphabet

Valid / Invalid Alphabet

Descriptive Definition of a Language

Exercises: Descriptive Definition of a Language

Exercises: Descriptive Definition of a Language

L1 = Language of all words as INTEGERS

Kleen Star Closure

Plus Operation (+)

You might also like