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 π.
0 Response to "What is a regular expression"
Post a Comment