Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

# TOC-grand test-Q1

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177
+1 vote

Consider the following languages

$\small L1 = \{x\#y: x, y \in \{0, 1\}*,\text{when viewed as binary numbers}, x+y = 3y\}.$

Example: $\small 1000\#100 \in L1$

Let $\small \Sigma = {a, b},$

$\small L2 = {w \in \Sigma*: (w \text{ contains the substring } ab)\rightarrow(\text{w contains the substring ba})}$

$\small L3 = \{w = xyzy : x, y, z \in \{0, 1\}^+ \}.$

$\small L4 = \{w = st : s \in \{a, b\}^* \text{and t }\in \{b, c\}^* \text{ and } \#b(s) = 2.\#a(s) \text{ and } \#c(t) = 3.\#b(t) \}$

$\small \text{(\#b(s) can be interpreted as number of b's in s)}$

Which of the above languages are REGULAR ?

(A) L1 and L4

(B) L2 and L3

(C) L2 , L3 and L4

(D) Only L3

edited Aug 27, 2020

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 = $100^k$#$10^k$. 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 = $0^p$ 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 $y\neq0$)

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 = $b^{2k}a^{k}c^{3k}b^{k}$￼ y must occur in the first b region. It is $b^p$, 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 $b^{2k-p}a^{k}c^{3k}b^{k}$￼. The s region is $b^{2k-p}a^{k}$. It doesn’t have twice as many b’s as a’s. So this string is not in L4.

Hence Option B

answered Sep 11, 2019 by (91,540 points)

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.

answered Sep 8, 2019 by (14,660 points)