What is a regular expression
1. 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.
2. 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 q0 q1
3. What
is Arden ’s
Theorem?
4. 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)]
5. 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*)*
6. 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,………………………………….}
7. 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)*
8. 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
9. 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)*
10. 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.
11. .Reg exp
for the language that accepts all strings in which ‘a’ appears tripled overthe
set Σ ={a}
reg exp=(aaa)*
12. .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 uvi
w is not in
L.Then L is not a regular language.
13. 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.
14. .Reg exp
for the language such that every string will have atleast one ‘a’ followed by atleast one ‘b’.
R=a+b+
15. Write the
exp for the language starting with and has no consecutive b’s .
reg exp=(a+ab)*
16. Lists on
the closure properties of Regular sets.
(i)
Union
(ii)
Concatenation
(iii)
Closure
(iv)
Complementation
(v)
Intersection
(vi)
Transpose
(vii)
Substitutions
(viii)
Homomorphism
17. Let R be
any set of regular languages. IsUR regular? Prove it.
Yes. Let P,Q be any two regular languages .As per
theorem
L( R )=L(P UQ)
=L(P+Q)
Since ‘+’ is a operator for regular expresstions L( R
) is also regular.
18. Show that
(r*)*=r* for a regular expression r,
(r*)*=={ε,r,rr,………….}= r*
19. What are
the three methods of conversion of DFA to RE?
(i)
Regular Expression equation method
(ii)
Arden ’s
Theorem.
(iii)
State elimination technique,
20. What are
the algorithms of minimization DFA?
(i)
Myhill-Nerode Theorem
(ii)
Construction of πfinal from π.