{a^nb^n|n≥0}

{a^mb^n|m,n≥0}

{a^nb^nc^n|n≥0}

{w∈{a,b}∗|w has equal number of a′s and b′s}

{a^2n|n≥0}

{a^nb^m|m≤n}

{a^((n+1)^2−n^2)|n≥0}

{a^n|n is odd}

Every language that satisfies the pumping lemma is regular

Every regular language satisfies the pumping lemma

A language that does not satisfy the pumping lemma is not regular

Some non-regular languages satisfy the pumping lemma

{a^p|p is a prime number}

{w∈{0,1}∗|w contains at most two 1's}

{w∈{0,1}∗|w ends with 00}

{w∈{0,1}∗| binary w is divisble by 5}

(10)∗

(01)∗

0∗1∗

0∗+1∗

1001

0110

1010

001100

S→aA A→bB B→aB|bB|ϵ

S→bA A→aB B→aB|bBϵ

S→aS|bS|ϵ

S→abS|ϵ

S→abaS|ϵ

S→aSbSa|ϵ

S→aSa|bSb|ϵ

S→abS|baS|ϵ

S→0S|1S|S0|S1|ϵ

S→SS|0|1

S→0S0|1S1|ϵ

S→A|B,A→0A|ϵ,B→1B|ϵ

S→aSa|bSb|a|b|ϵ

S→aSb|bSa|ϵ

S→aS|bS|ϵ

S→aaS|bbS|a|b

a) A → a or A → BC

b) A → aB or A → ε

c) A → aB | a

d) A → AB | aB

a) { a^n b^n | n ≥ 1 }

b) { a^m b^n | m, n ≥ 1 }

c) { a^n b^n | n ≥ 0 }

d) { a^n b^n | n ≥ 2 }

a) Every regular language is also context-free.

b) Every context-free language is also regular.

c) Context-free languages are closed under intersection with each other.

d) Context-free languages are closed under complementation.

a) { a^n b^n | n ≥ 0 }

b) { a^n b^m | n, m ≥ 0 }

c) { w ∈ {a, b}* | w has equal a’s and b’s }

d) { a^n b^n c^n | n ≥ 0 }

a) S → aS | bS | ε

b) S → Sa | Sb | ε

c) S → AB, A → a, B → b

d) S → aSb

a) Every production is of the form A → aB or A → a

b) Every production is of the form A → BC

c) Every production is of the form A → aB | ε

d) Both (a) and (c)

a) It is accepted by a DFA

b) It has finitely many equivalence classes under the relation ≡L

c) It is closed under union and intersection

d) It can be expressed by a right-linear grammar

a) x and y have the same length

b) x and y lead to the same state in DFA for L

c) For all z ∈ Σ*, xz ∈ L ⇔ yz ∈ L

d) x and y have the same number of symbols

a) The number of productions in its grammar

b) The number of states in the minimal DFA for L

c) The number of terminal symbols in Σ

d) The length of the longest string in L

a) 2

b) 3

c) 4

d) Infinite

a) Finitely many equivalence classes → L is regular

b) Infinitely many equivalence classes → L is not regular

c) Equivalence classes equal to n

d) A DFA with 2 states

a) 2

b) 3

c) Infinite

d) 6

a) Designing CFGs

b) Checking ambiguity of grammars

c) Proving that a language is not regular

d) Removing ε-productions

a) L = { w ∈ {a, b}* | w has equal number of a’s and b’s }

b) L = { a^n b^n | n ≥ 0 }

c) L = { a^n b^m | n, m ≥ 0 }

d) Both (a) and (b)

a) Unique

b) Not unique

c) May not exist

d) Depends on construction

a) 2

b) 3

c) 4

d) 5

a) L1 ∪ L2

b) L1 ∩ L2

c) L1 L2

d) L1 ∩ L where L is a CFL

a) Unambiguous and generates {a^n | n ≥ 1}

b) Ambiguous and generates {a^n | n ≥ 1}

c) Ambiguous and generates {a^n b^n | n ≥ 1}

d) Unambiguous and generates {a^n b^n | n ≥ 1}

S → aS | Sb | ε

S → aS | b

S → aSb | ε

S → aA, A → bA | ε

c) { a^n b^n | n ≥ 1 }

d) { a^n b^m | n = m }

b) { a^n b^m | n, m ≥ 0 }

a) { a^n b^n | n ≥ 0 }

a) 1

b) 2

c) 3

d) 4

c) Context-free languages are closed under intersection with regular languages.

a) Every context-free language can be represented by a pushdown automaton.

d) Context-free languages are closed under complementation.

b) Context-free languages are closed under union.

States having the same number of incoming transitions

States with the same number of outgoing transitions

Final vs Non-final states

d)States having same alphabet symbols

Number of transitions in DFA

Number of equivalence classes under Myhill–Nerode relation

Number of terminals in alphabet Σ

Length of longest accepted string

1

log₂ n

√n

n/2

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

{ a^n b^m | n, m ≥ 0 }

{ (ab)* }

{ a, b }*

(i) True, (ii) True

(i) True, (ii) False

(i) False, (ii) True

(i) False, (ii) False

|Σ|

The number of equivalence classes under ≡L

The number of productions in grammar

The number of terminal symbols

1(0*11)*

0(0+1)*

1(0+11)*

1(110*)*