Every Finite Automata accept a string which is represented by an expression is called Regular Expression.
EXAMPLE 1:
an , n >= 0
(a0 , a, aa , aaa ......)
Accepted Strings are : ( ε , a , aa , aaa, ...)
EXAMPLE 2 :
Accepted Strings are : ( a , aa , aaa , ...)
Now the General Expression will be : an , n > = 1
We can say that :
Generalised format of string which is accepted by Finite Automata is called Regular Expression (RE)
EXAMPLE:
BASIC CLOSURE PROPERTIES OF REGULAR EXPRESSION (RE)
1. Kleen closure (*):
Suppose a be any regular expression and, if we a* write which is equal to
If the value of i=0 the value of a = ε then ( ε , a , aa , aaa, ...)
Acceptable value of any RE is combine in a set is called regular set.
OR
Regular set contain set of acceptable values of any RE.
So Regular Set = ( ε , a , aa , aaa, ...)
2. Positive closure (+):
If a be any regular expression and if we write a+ this is equivalent to
i.e a+ contain at least one a
Regular Set (RS) = ( a , aa , aaaa , ........ )
Note : ε is not included
a* = any number of a's possibly ε
a+ = any number of a's but contain at last one a.
Relation between a* & a+
Let we proof above relation
First take RHS = ( a ) ( a* )
= ( a , aa , aaa , ......)
= a+
therefore LHS = RHS hence proved.
QUESTIONS FOR PRACTICE
1. Construct a regular set (RS) for following:
a. (01)*
Solution: RS = ( ε , 01, 0101, 010101, ...... )
b. ( 0 + 1 )
Solution: Note here + means union (U)
(0) U (1) → ( 0,1)
c. 01*
Solution: RS = (0) ( ε, 1, 11, 111, .....)
= (0, 01, 011, 0111, .....)
d. (01)* + 0
Solution: RS = ( ε , 01, 0101, 010101, ...... ) U (0)
= ( ε , 01, 0101, 010101, ...... , 0)
e. (0 + 1)*
Solution: RS = ( 0 )* U ( 1)*
= ( ε , 0, 00, 000, ...... ) U ( ε , 1, 11, 111, ...... )
= ( 0 ) U ( ε , 1, 11, 111, ...... )
RS = ( ε , 1, 11, 111, ...... , 0 )
f. (0+1)+
Solution: RS = (0)+ U (1)+
= (0) U (1, 11, 111, ..... )
= (1, 11, 111, ..... , 0 )
RE for string of 0's and 1's contain at least one symbol.
2. Prove that
ε + 11+ =1*
Proof:
let we take LHS
i.e ε + 11+
= ( ε ) U (1) ( ε , 1, 11, 111, ...... )
= ( ε , 1, 11, 111, ...... )
= 1*
Now LHS = RHS
Hence proved
3. Prove that
0 (10)* = (01)* 0 are equal
Proof:
Let we take LHS = 0 (10)*
= (0) ( ε , 10, 1010, 101010, ...... )
LHS = ( 0, 010, 01010, 0101010, ...... )
Now take RHS = (01)* 0
= ( ε , 01, 0101, 010101, ...... ) (0)
RHS = ( 0 , 010, 01010, 0101010, ...... )
Here LHS =RHS
Hence Proved.
4. Construct a regular expression which accept string of 0's and 1's ends with sub string 00.
Solution:
Let we understand pattern of string ask in question such as :
100 ---- Accepted ✔
1100 ---- Accepted ✔
0100 ---- Accepted ✔
01001 ---- Not Accepted ❌
So the regular expression for such a pattern will be:
RE = (0 + 1)* (00)
5. Construct a regular expression which accept string of 0's and 1's contain consecutive 0's.
Solution :
Let we understand pattern of string ask in question such as :
10001 ---- Accepted ✔
11000 ---- Accepted ✔
01000 ---- Accepted ✔
010010 ---- Not Accepted ❌
So the regular expression for such a pattern will be:
RE = (0 + 1)* (000) (0 + 1)*
6. Construct a regular expression which accept a string of a's and b's which contain even number of a's followed by odd number of b's.
Solution:
Note : minimum number of a's =0
minimum number of b's=1
Let we understand pattern of string ask in question such as :
b ---- Accepted ✔
aab ---- Accepted ✔
aabbb ---- Accepted ✔
aaaab ---- Accepted ✔
aaaabbb ---- Accepted ✔
aabb ---- Not Accepted ❌
aaaabb ---- Not Accepted ❌
So the regular expression for such a pattern will be:
RE = (aa)* (b) (bb)*
OR
RE = a* (a + b)* b+
7. Construct a regular expression which accept a string of a's and b's contain at most two a's.
Solution:
Note : minimum number of a's =0
maximum number of a's=2
Let we understand pattern of string ask in question such as :
b ---- Accepted ✔
aab ---- Accepted ✔
abab ---- Accepted ✔
aabb ---- Accepted ✔
abbb ---- Accepted ✔
ababba ---- Not Accepted ❌
abaaba ---- Not Accepted ❌
So the regular expression for such a pattern will be:
RE = b* + b* a b* + b* a b* a b*
8. Construct a regular expression which accept a string of a's and b's start and end with same symbols.
Solution:
RE = a + b + a (a + b)* a + b (a + b)* b
9. Construct a regular expression which accept binary integer divisible by 2.
Solution:
RE = (0 + 1)* 0
10. Construct a regular expression which accept string of a's and b's contain one a's and two b's.
Solution:
RE = abb + bab + bba
This post is all about regular expression i hope you all understand and it useful for you all.
No comments:
Post a Comment