1. Why are switching
circuits called as finite state systems?
A switching circuit consists of
a finite number of gates ,each of which can be in any one of the two conditions
0 or 1.Although the voltages assume infinite set of values ,the electronic
circuitry is designed so that the voltages corresponding to 0 or 1 are stable
and all others adjust to these value. Thus control unit of a computer is a finite state system.
2.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 .
3.Define: (i) Finite
Automaton(FA) (ii)Transition diagram
FA consists of a finite set of
states and a set of transitions from state to state that occur on input symbols
chosen from an alphabet ∑. Finite Automaton is denoted by a
5- tuple(Q,∑,δ,q0,F), where Q
is the finite set of states , ∑ is a finite input alphabet, q0 in Q is the
initial state, F is the set of final states and
δ is the transition mapping function
Q * Σ to Q.
Transition diagram is a directed
graph in which the vertices of the graph correspond to the states of FA. If
there is a transition from state q to state p on input a, then there is
an arc labeled ‘ a ‘ from q to p in the transition diagram.
4. What are the applications of automata theory?
Ø
In compiler
construction.
Ø
In switching
theory and design of digital circuits.
Ø
To verify the
correctness of a program.
Ø
Design and
analysis of complex software and hardware systems.
Ø
To design finite
state machines such as Moore and mealy machines.
5. What is Moore machine
and Mealy machine?
A special case of FA is Moore machine in which the output
depends on the input and state of the machine.
An automaton in whch the output
depends on the transition and current input is called Mealy machine.
6.What are the components of Finite automaton model?
The components of FA model are
Input tape, Read control and finite control.
(a)The input tape is divided into
number of cells. Each cell can hold one i/p symbol.
(b)The read head reads one symbol at a
time and moves ahead.
( c)Finite control acts like a CPU.
Depending on the current state and input symbol
read from the input tape it
changes state.
7.Differentiate NFA and
DFA
NFA or Non Deterministic Finite
Automaton is the one in which there exists many paths for a specific input from
current state to next state. NFA can be
used in theory of computation because they
are more flexible and easier to use than DFA.
Deterministic Finite Automaton
is a FA in which there is only one path for a specific input from current state
to next state. There is a unique
transition on each input symbol.(Write examples with diagrams).
8.What is Є-closure of a
state q0?
Є-closure(q0 ) denotes a set of all vertices p such that
there is a path from q0 to p labeled Є. Example
:
Є-closure(q0)={q0,q1}
9.What is a : (a) String
(b) Regular language
A string x is accepted by a Finite Automaton
M=(Q,Σ,δ.q0,F) if δ(q0,x)=p, for some p
in F.FA accepts a string x if the sequence of transitions corresponding to the
symbols of x leads from the start state
to accepting state.
The language accepted by M is
L(M) is the set {x | δ(q0,x) is in F}. A language is regular if it is accepted
by some finite automaton.
10.What is a regular expression?
A regular expression is a string
that describes the whole set of strings according to certain syntax rules.
These expressions are used by many text editors and utilities to search bodies
of text for certain patterns etc. Definition is: Let Σ be an alphabet. The regular expression over Σ
and the sets they denote are:
i.
Φ is a r.e and
denotes empty set.
ii.
Є is a r.e and
denotes the set {Є}
iii.
For each ‘a’ in Σ
, a+ is a r.e and denotes the set {a}.
iv.
If ‘r’ and ‘s’
are r.e denoting the languages R and S respectively then (r+s),
(rs)
and (r*) are r.e that denote the
sets RUS, RS and R*
respectively.
11. Differentiate L* and
L+
∞
L* denotes Kleene closure and is given by L* =U Li
i=0
example : 0* ={Є ,0,00,000,…………………………………}
Language includes empty words
also.
∞
L+ denotes Positive closure
and is given by L+= U Li
i=1
example:0+={0,00,000,……………………………………..}
12.What
is Arden’s Theorem?
Arden’s theorem helps in
checking the equivalence of two regular expressions.
Let P and Q be the two
regular expressions over the input alphabet Σ. The regular expression R is given as :
R=Q+RP
Which has a unique solution as R=QP*.
13.Write a r.e to
denote a language L which accepts all
the strings which begin or
end with either 00 or 11.
The r.e consists of two parts:
L1=(00+11) (any no of 0’s
and 1’s)
=(00+11)(0+1)*
L2=(any no of 0’s and
1’s)(00+11)
=(0+1)*(00+11)
Hence r.e R=L1+L2
=[(00+11)(0+1)*]
+ [(0+1)* (00+11)]
14.Construct a r.e for the
language which accepts all strings with atleast two c’s over
the set Σ={c,b}
(b+c)* c (b+c)* c (b+c)*
15.Construct a r.e for
the language over the set Σ={a,b} in
which total number of
a’s
are divisible by 3
( b* a b* a
b* a b*)*
16.what is: (i)
(0+1)* (ii)(01)* (iii)(0+1) (iv)(0+1)+
(0+1)*= { Є , 0 , 1 , 01 , 10 ,001 ,101 ,101001,…………………}
Any combinations of 0’s and 1’s.
(01)*={Є , 01 ,0101 ,010101
,…………………………………..}
All combinations with the
pattern 01.
(0+1)= 0 or 1,No other
possibilities.
(0+1)+=
{0,1,01,10,1000,0101,………………………………….}
17.Reg exp denoting a
language over Σ ={1} having
(i)even length of string (ii)odd length of a string
(i) Even length of string R=(11)*
(ii) Odd length of the string
R=1(11)*
18.Reg exp for:
(i)All strings over
{0,1} with the substring ‘0101’
(ii)All strings
beginning with ’11 ‘ and ending with ‘ab’
(iii)Set of all strings over
{a,b}with 3 consecutive b’s.
(iv)Set of all strings
that end with ‘1’and has no substring ‘00’
(i)(0+1)* 0101(0+1)*
(ii)11(1+a+b)* ab
(iii)(a+b)* bbb (a+b)*
(iv)(1+01)* (10+11)* 1
19. What are the
applications of Regular expressions and Finite automata
Lexical analyzers and Text
editors are two applications.
Lexical analyzers:The tokens of
the programming language can be expressed using regular expressions. The
lexical analyzer scans the input program and separates the tokens.For eg
identifier can be expressed as a regular expression as:
(letter)(letter+digit)*
If anything in the source
language matches with this reg exp then it is recognized as an identifier.The
letter is{A,B,C,………..Z,a,b,c….z} and digit is {0,1,…9}.Thus reg exp identifies
token in a language.
Text editors: These are
programs used for processing the text.
For example UNIX text editors uses the reg exp for substituting the strings
such as:
S/bbb*/b/
Gives the substitute a single
blank for the first string of two or
more blanks in a given line. In UNIX text editors any reg exp is converted to
an NFA with Є –transitions, this NFA can be then simulated directly.
20.Reg exp for the
language that accepts all strings in which ‘a’ appears tripled over
the set Σ ={a}
reg exp=(aaa)*
21.What are the
applications of pumping lemma?
Pumping lemma is used to check if a language is
regular or not.
(i)
Assume that the
language(L) is regular.
(ii)
Select a constant
‘n’.
(iii)
Select a
string(z) in L, such that |z|>n.
(iv)
Split the word z
into u,v and w such that |uv|<=n and |v|>=1.
(v)
You achieve a
contradiction to pumping lemma that there exists an ‘i’
Such
that uviw is not in L.Then L is not a regular language.
22. What is the closure
property of regular sets?
The regular sets are closed under union, concatenation and Kleene
closure.
r1Ur2= r1 +r2
r1.r2= r1r2
( r )*=r*
The class of regular sets are closed
under complementation, substitution, homomorphism and inverse homomorphism.
23.Reg exp for the
language such that every string will have atleast one ‘a’ followed
by atleast one ‘b’.
R=a+b+
24.Write the exp for the
language starting with and has no consecutive b’s
reg exp=(a+ab)*
