AUTOMATA

1.  What are the applications of TOC?

Compiler Design

Robotics

Artificial Intelligence

Knowledge Engineering.

2.  Define Transition Diagram.

Transition Diagram associated with DFA is a directed graph whose vertices corresponds to states of DFA, The edges are the transitions from one state to another.

3. What are the properties of Transition Function(δ)

(i)                 δ(q.ε )=q

(ii)               For all strings w and input symbol a

                Δ(q,aw)= δ(δ(q.a),w)

  Δ(q,wa)= δ(δ(q,w).a)

(i)                 The transition function δ can be extended that operates on states and strings.

2. Lists the operations on Strings.

(i)                 Length of a string

(ii)               Empty string

(iii)             Concatenation of string

(iv)             Reverse of a string

(v)               Power of an alphabet

(vi)             Kleene closure

(vii)           Substring

(viii)         Palindrome

3.  Lists the operations on Languages.

(i)                 Product

(ii)               Reversal

(iii)             Power

(iv)             Kleene star

(v)               Kleene plus

(vi)             Union

(vii)           Intersection

4. Define Graphs.

A graph denoted by G=(V,E) consists of a finite set of vertices (or) nodes V and a set E, a pair of vertices called edges.

5. Define Substring.

A string v appears within another string w(w=uv) is called “substring of w.” IF w=uv,then substrings u & v are said to be prefix and suffix of w respectively.

6. Give the examples/applications designed as finite state system.

               Text editors and lexical analyzers are designed as finite state systems. A  lexical analyzer scans the symbols of a program to locate strings corresponding to identifiers, constants etc, and it has to remember limited amount of information .