My friend is interested in computations of machines, and wants to see if he can

Question

My friend is interested in computations of machines, and wants to see if he can find a "repeating" pattern during such a computation. Formally, observe the language (#W_1 #W_2 # ellipsis #W_k #: W_1 belongs to (0, 1)^*, 1 lessthanorequalto i lessthanoreqaulto k, and for some i notequalto j, W_i = W_j). My friend believes that this language is context-free, is it? It is not context-free because a PDA to recognize it would have to match all possible choices of 2 strings and check equality. It is not context-free because the string #0^p 1^p #0^p 1^p # pumps out of the language and therefore shows the necessary contradiction. It is context-free because this is just (0^1^n: n greaterthanorequalto 0)^+ separated by # symbols. It is text-free because this is just a subset of another CFL we have been in class. None of the above.

Explanation / Answer

It is not a CFL, because a PDA to recognize it would have to match all possible choices of 2 strings and has to check equality.

Here given that for some i!=j wi=wj, so there are some equal words.

#w1#w2#w3#w4......#wk#, so there are k words in which some words are equal, so every word is to be compared with every other wors from the word1 it has to compare all words up to wordk for checking the equality.

so it takes k2 comparasions, but PDA has only one stack, so it can't be implemented with one stack.

PDA has only one stack.

so it is not a CFL.

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

---

---

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