Let M = (Q, Sigma, delta, q_1, F) be a DFA recognizing A and p be the number of

Question

Let M = (Q, Sigma, delta, q_1, F) be a DFA recognizing A and p be the number of states of M. Let s = s_1s_2 ... s_n be a string in A of length n, where n Greaterthanorequalto p. Let r_1, ..., r_n+1 be the sequence of states that M enters; while processing s, so r_i+1 = delta(r_i, s_i) for 1 lessthanorequalto i lessthanorequalto n. This sequence has length n + 1, which is at least p +1. Among the first p +1 elements in the sequence, two must be the same state, by the pigeonhole principle. We call the first of these r_j and the second r_l. Because r_l occurs among the first p + 1 places in a sequence starting at r_1, we have 1 lessthanorequalto p + 1. Now let x = s_1 ... s_j - 1, y = s_j ... s_l - 1 z = s_1 ... s_n. As x takes M from r_1 to r_j, y takes M from r_j to r_j, and z takes M from r_j to r_n+1, which is an accept state, M must accep xy^iz for i Greaterthanorequalto 0. We know that j NotEqual l, so |y| > 0; and l lessthanorequalto p + 1, so |xy| lessthanorequalto p. Thius we have satisfied all conditions of the pumping lemma.

Explanation / Answer

ok I understood what you actually want I will explain you those notations below:

   here n+1 term is used denote the number of states that goes through to check the satisfiability of the string whose length is n. Here there are p states in the machine and while processing string of length n where p<=n then every state will occur at least once.

here i+1 is used to represent the next state while processing the string ..... if a character at state 1 makes a move to state 2 then i=1 and i+1=2

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.