Assignment about L1 – L2 is regular.

Question 1: L1 – L2 is regular.
Proof: We here knows that L1-L2= L1∩L2
Given in the question that L1 and L2 are regular.
Consider, for regular expression L1, AL1 is the DFA and for regular expression L2,
AL2 is the DFA respectively.
This follows,
AL1 = (Q, Σ, δ, q0, F) is represented by L1.
And, AL2 = (Q, Σ, δ, q0, Q − F) is represented by L1.
We know that under union and complement regular languages are closed it implies
that L 1U L 2= L1 ∩ L2 is a regular language.
Question 2: Convert Regular Expression to Finite
Automata:
Here provided regular expression is:
RE = (00 + 11 + (01 + 10)(00 + 11)*(01 + 10))*
The above Regular Expression is of EVEN- EVEN Language Regular expression.
It can accepts only even number of 0’s and 1’s: 00, 11, 0101, 1100, 0011, 1010,
100001..
Step 1 – If no 0 and 1 is present (empty) then also it is accepted, hence the first
state is q0 :

Step 2: Based on the above example provided it can also accept 00: (state q1 is
introduced)
Step 3: Similarly 11 is also accepted by the machine: (state q2 is introduced)
Step 4: It can accept 10 01 and multiple of it hence new state q3 will be introduced.

Hence the above figure is the finite automata for the given Regular expression - (00
+ 11 + (01 + 10)(00 + 11)*(01 + 10))*.
Question 3:
a. {www | w is {a,b}*}
Here to prove that provided expression is not regular, we use the proof of
contradiction. We will assume the language provided is regular.
Let the L = {www | w is {a,b}*} and also L is regular. Hence L is regular than there
is a pumping length exists for it “p” (such that string s ∈ L when |s| ≥ p). Below are
the conditions which s=xyz need to follow:
Let’s consider string s= apbbapb, as it is Regular expression hence all the above
conditions are fulfilled in it:
As per the 1st condition, it is concluded that y=0k for value of k>0, and as per 2nd
condition it can be concluded that s is composed of x and y and as per condition 3 it
can take any value of i. Let’s take i=2 and resulting string will be in expression L.
Hence xy2z should be in L and xy2z = xyyz = a(p+k)bbapb.