###### Aptitude

October 12, 2023###### Theory-of-Computation

October 12, 2023# Theory-of-Computation

Question 2 |

For Σ = {a,b}, let us consider the regular language L = {x|x = 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.

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.

Subscribe

Login

0 Comments