Aptitude
October 12, 2023TheoryofComputation
October 12, 2023TheoryofComputation
Question 2

For Σ = {a,b}, let us consider the regular language L = {xx = a^{2+3k} or x = b^{10+12k}, k ≥ 0}. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?
3


9


5


24

Question 2 Explanation:
Pumping Lemma for Regular Languages:
For any language L, there exists an integer n, such that for all x ∈ L with x ≥ n, there exists u,v, w ∈ Σ*, such that x = uvw, and
(1) uv ≤ n
(2) v ≥ 1
(3) for all i ≥ 0: uv^{i}w ∈ L
We have to find “n” which satisfies for all the strings in L.
Considering strings derived by b^{10+12k}.
The minimum string in L = “bbbbbbbbbb” but this string b^{10} cannot be broken in uvw.
So, pumping length 3, 9 and 5 cannot be the correct answer.
So, the minimum pumping length, such that any string in L can be divided into three parts “uvw” must be greater than 10.
For any language L, there exists an integer n, such that for all x ∈ L with x ≥ n, there exists u,v, w ∈ Σ*, such that x = uvw, and
(1) uv ≤ n
(2) v ≥ 1
(3) for all i ≥ 0: uv^{i}w ∈ L
We have to find “n” which satisfies for all the strings in L.
Considering strings derived by b^{10+12k}.
The minimum string in L = “bbbbbbbbbb” but this string b^{10} cannot be broken in uvw.
So, pumping length 3, 9 and 5 cannot be the correct answer.
So, the minimum pumping length, such that any string in L can be divided into three parts “uvw” must be greater than 10.
Correct Answer: D
Question 2 Explanation:
Pumping Lemma for Regular Languages:
For any language L, there exists an integer n, such that for all x ∈ L with x ≥ n, there exists u,v, w ∈ Σ*, such that x = uvw, and
(1) uv ≤ n
(2) v ≥ 1
(3) for all i ≥ 0: uv^{i}w ∈ L
We have to find “n” which satisfies for all the strings in L.
Considering strings derived by b^{10+12k}.
The minimum string in L = “bbbbbbbbbb” but this string b^{10} cannot be broken in uvw.
So, pumping length 3, 9 and 5 cannot be the correct answer.
So, the minimum pumping length, such that any string in L can be divided into three parts “uvw” must be greater than 10.
For any language L, there exists an integer n, such that for all x ∈ L with x ≥ n, there exists u,v, w ∈ Σ*, such that x = uvw, and
(1) uv ≤ n
(2) v ≥ 1
(3) for all i ≥ 0: uv^{i}w ∈ L
We have to find “n” which satisfies for all the strings in L.
Considering strings derived by b^{10+12k}.
The minimum string in L = “bbbbbbbbbb” but this string b^{10} cannot be broken in uvw.
So, pumping length 3, 9 and 5 cannot be the correct answer.
So, the minimum pumping length, such that any string in L can be divided into three parts “uvw” must be greater than 10.
Subscribe
Login
0 Comments