9)Define Pumping Lemma. Prove that below language is not a regular Language. L ={ ai bj | i > j }:-Let L be a regular language. There exists a constant k such that for every string ω in L, such that length of string ω i.e |ω| ≥ k, we can break ω into 3 strings i.e ω = xyz following conditions:ll(i) |xy| ≤ k ll(ii) y ≠ ε i.e |y| > 0ll(iii) for each q ≥ 0, xy^qz ∈ Lll Let L be regular language ll w = a^(k+1) b^k a long string (∵ given k > 0) ll |w| = 2k + 1, w = xyz should satisfy ll (i) |xy| ≤ k ll (ii) y ≠ 0 ll (iii) for each q ≥ 0, xy^q z ∈ L ll Let k = 3 ll,w = a^4 b^3 ll aaaaabbb ll (i) |xy| ≤ k ll 3 ≤ 3 ll (ii) y ≠ 0 ll y = a ll 
10) table filling algorithm :-BASIS: If pp is an accepting state and qq is nonaccepting, then the pair {p,q}\{p, q\} is distinguishable.ll INDUCTION: Let pp and qq be states such that for some input symbol aa, r=δ(p,a)r = \delta(p, a) and s=δ(q,a)s = \delta(q, a) are a pair of states known to be distinguishable. Then {p,q}\{p, q\} is a pair of distinguishable states. The reason this rule makes sense is that there must be some string ww that distinguishes rr from ss; that is, exactly one of δ^(r,w)\hat{\delta}(r, w) and δ^(s,w)\hat{\delta}(s, w) is accepting. Then string awaw must distinguish pp from qq, since δ^(p,aw)\hat{\delta}(p, aw) and δ^(q,aw)\hat{\delta}(q, aw) is the same pair of states as δ^(r,w)\hat{\delta}(r, w) and δ^(s,w)\hat{\delta}(s, w).ll
11)Minimization of DFA’s A=(Q, ∑, δ, qo, F) :-Use the table-filling algorithm to find all the pairs of equivalent states.llPartition the set of states QQ into blocks of mutually equivalent states ll construct the minimum-state equivalent DFA BB by using the blocks as its states. Let γ\gamma be the transition function of BB. Suppose SS is a set of equivalent states of AA, and aa is an input symbol. Then there must exist one block TT of states such that for all states qq in SS, δ(q,a)\delta(q, a) is a member of block TT. we can let γ(S,a)=T\gamma(S, a) = T. In addition ll (a) The start state of BB is the block containing the start state of AA ll (b) The set of accepting states of BB is the set of blocks containing accepting states of AA. Note that if one state of a block is accepting, then all the states of that block must be accepting.ll12)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. ll Constructing Parse Trees :-Let us consider a grammar G=(V, T, P, S). The parse trees for G are trees with the following conditions: ll1. Root of the tree is labelled by start symbol S of the grammar ll 2. Each interior node is labeled by a variable in V.ll 3. Each leaf is labeled by either a variable, a terminal, or ε. However, if the leaf is labelled ε, then it must be the only child of its parent. 4. If an interior node is labeled A, and its children are labeled X 1 , X2, ……………., X k llExample: Consider the following grammar :-
