Pumping Lemma, Table Filling, DFA Minimization, Parse Trees, Ambiguous Grammars & Context-Free Grammars

Pumping Lemma and Non-Regular Languages

9) Define Pumping Lemma. Prove that the language L = { aⁱ b^j | i > j } is not a regular language:

Let L be a regular language. There exists a constant k such that for every string ω in L, where the length of string ω i.e |ω| ≥ k, we can break ω into 3 strings i.e ω = xyz following conditions:

• (i) |xy| ≤ k
• (ii) y ≠ ε i.e |y| > 0
• (iii) for each q ≥ 0, xy^qz ∈ L

Let L be a regular language. w = a^(k+1) b^k is a long string (given k > 0). |w| = 2k + 1, w = xyz should satisfy:

• (i) |xy| ≤ k
• (ii) y ≠ 0
• (iii) for each q ≥ 0, xy^q z ∈ L

Let k = 3, w = a⁴ b³, which is aaaaabbb.

• (i) |xy| ≤ k, 3 ≤ 3
• (ii) y ≠ 0, y = a

Minimization of DFA's

11) Minimization of DFA’s A=(Q, Σ, δ, q₀, F):

Use the table-filling algorithm to find all the pairs of equivalent states.

Partition the set of states Q into blocks of mutually equivalent states.

Construct the minimum-state equivalent DFA B by using the blocks as its states. Let γ be the transition function of B. Suppose S is a set of equivalent states of A, and a is an input symbol. Then there must exist one block T of states such that for all states q in S, δ(q,a) is a member of block T. We can let γ(S,a) = T. In addition:

• (a) The start state of B is the block containing the start state of A.
• (b) The set of accepting states of B is the set of blocks containing accepting states of A. Note that if one state of a block is accepting, then all the states of that block must be accepting.

Parse Trees

12) Parse Trees:

There is a tree representation for derivations that has proved extremely useful. This tree shows us clearly how the symbols of a terminal string are grouped into substrings, each of which belongs to the language of one of the variables of the grammar.

Constructing Parse Trees:

Let us consider a grammar G=(V, T, P, S). The parse trees for G are trees with the following conditions:

1. Root of the tree is labeled by start symbol S of the grammar.
2. Each interior node is labeled by a variable in V.
3. Each leaf is labeled by either a variable, a terminal, or ε. However, if the leaf is labeled ε, then it must be the only child of its parent.
4. If an interior node is labeled A, and its children are labeled X₁, X₂, ..., X_k

Example: Consider the following grammar:

Ambiguous Grammars

13) What is an ambiguous grammar? Explain the techniques for reducing ambiguity in the grammar with suitable examples:

A grammar G is ambiguous if and only if there exists at least 1 string w ∈ L(G) for which two or more different parse trees exist by applying LMD/RMD.

Techniques for reducing ambiguity in grammar with example:

Removing ambiguity from arithmetic expression can be removed by considering the precedence of operators in the following order:

• Identifier - a, b, c (highest)
• Parenthesis ( )
• Multiplication & division ( *, / )
• Associativity is considered from left to right

The grammar can be written as:

Σ -> a | b | c

F -> (E) | I

T -> T*F | T/F | F

E -> E+T | E-T | T

Rearrange the production from each symbol:

E -> E+T | E-T | T

T -> T*F | T/F | F

F -> (E) | I

Σ -> a | b | c

14) Show that the following grammar is ambiguous by taking the string aab. S → aS | aSbS | ε :

Context-Free Grammars

15) Design the Context-Free Grammar for the following Languages:

i) To accept the set of all strings with no more than three a’s when Σ = {a, b}.

ii) To accept the set of strings with any number of a’s and b’s with at least one a.