Virtual Labs

Identify Non Context-free Language using Pumping Lemma

What is the primary use of the Pumping Lemma for context-free languages?

a: To prove that some languages are not context-free. Explanation

Explanation

b: To minimize context-free grammars. Explanation

Explanation

c: To generate new context-free grammars. Explanation

Explanation

d: To determine closure properties of CFLs. Explanation

Explanation

Which type of languages does the Pumping Lemma for CFLs specifically apply to?

a: All formal languages. Explanation

Explanation

b: Only regular languages. Explanation

Explanation

c: Context-free languages. Explanation

Explanation

d: Context-sensitive languages. Explanation

Explanation

When applying the Pumping Lemma for CFLs, a string S is divided into five parts: S = uvxyz. Which condition must always hold?

a: |vy| > 0 Explanation

Explanation

b: |vxy| ≤ p Explanation

Explanation

c: u and z must always be empty Explanation

Explanation

d: v and y must be identical substrings Explanation

Explanation

What does 'pumping' a string in the context of the Pumping Lemma mean?

a: Repeating the substrings v and y any number of times while keeping u, x, and z fixed. Explanation

Explanation

b: Generating new productions in the grammar. Explanation

Explanation

c: Replacing all terminals with variables. Explanation

Explanation

d: Eliminating ambiguity in derivations. Explanation

Explanation

Which of the following languages can be proven NOT to be context-free using the Pumping Lemma?

a: { a^n b^n c^n | n ≥ 0 } Explanation

Explanation

b: { a^n b^n | n ≥ 0 } Explanation

Explanation

c: { a^i b^j | i, j ≥ 0 } Explanation

Explanation

d: { ww^R | w ∈ {a, b}* } Explanation

Explanation

What limitation of the Pumping Lemma should be kept in mind when using it?

a: It can only prove that a language is not context-free, not that it is context-free. Explanation

Explanation

b: It always requires a deterministic grammar. Explanation

Explanation

c: It applies only to finite languages. Explanation

Explanation

d: It guarantees closure properties of CFLs. Explanation

Explanation