TOC-grand test-Q1

Question

Consider the following languages

Example:

Let

Which of the above languages are REGULAR ?

(A) L1 and L4

(B) L2 and L3

(C) L2 , L3 and L4

(D) Only L3

Answer 1

L1 : Not regular, which we show using the Pumping Theorem. We must start by choosing a string that is in fact in L. L

w = #. Then w ∈ L since x (100^k) is equal to 2y (where y is 10^k). We must consider three cases for where y can fall:

y = 1 Pump out. Arithmetic is wrong.The left side is 0 but the right side isn't. 

y = 10* Pump out. Arithmetic is wrong. " The left side is 0 but the right side isn't. 

y =  Pump out. Arithmetic is wrong. Decreased left side but not right. So, in particular, it is no longer the case that x > y (required since )

L2 : Regular. 

It helps to rewrite L2 as: 
L2 = {w ∈ Σ*: ¬(w contains the substring ab) ∨ (w contains the substring ba)}

L2 = b*a* ∪ (a ∪ b)* ba (a ∪ b)*

L3 : Regular. 

The key to why this is so is to observe that we can let y be just a single character. Then the rest of w can generated by x and z. So any string w in {0, 1}+ is in L3 iff: 

• the last letter of w occurs in at least one other place in the string, 
• that place is not the next to the last character, 
• nor is it the first character, and 
• w contains least 4 letters. 

Either the last character is 0 or 1. So:

L3 = ((0 ∪ 1)+ 0 (0 ∪ 1)+ 0) ∪ ((0 ∪ 1)+ 1 (0 ∪1)+ 1).

L4 : Not regular, which we show by pumping. Let w =  y must occur in the first b region. It is , for some nonzero p. Note that, when we pump, the boundary between the s and t regions cannot move because there can be no a’s in s or c’s in t. Let q = 0 (i.e., pump out). The resulting string is . The s region is . It doesn’t have twice as many b’s as a’s. So this string is not in L4.

Hence Option B

 

 

 

 

Answer 2

ANS SHOULD BE D.

L2- It is an implication condition , so it will have 2 cases, in first no of  (ab)'s equal's to no of (ba) so here infinite comparsion so it will be dcfl. Second when when "it contain substring (ab)" is false will be Rl. Therefore union will be DCLF. Not RL.

L3- Yes it is regular.  

L4- Here also comparsion exists in s and t.