(DFA Outputs) We only defined a DFA to either \"accept\" or \"not accept\" a str

Question

(DFA Outputs) We only defined a DFA to either "accept" or "not accept" a string, based on whether the machine, when reading that string, ended in a final state or not. Consider a variant called an Output-DFA: it is a 6-tuple (Q, sigma, Gamma, delta, q_0, F) where Q, sigma, q_0, F are defined exactly as in a normal DFA, but gamma is the output alphabet, and delta: Q times sigma times (Gamma Union {epsilon}) rightarrow Q is the transition function. In other words, we associate either a character of Gamma or epsilon the "output" of executing that transition. We commonly write a transition of this form as q q' where a is the character read, and b is the character outputted. For such an Output-DFA M d w elementof sigma*, let M(w) be the concatenation of the characters outputted on each transition taken, and the machine only outputs anything if and only if the machine has read all of its input. If M has language L, let Out(M) = {M(w): w elementof L}. (a) Prove that if L is regular, then Out(M) is regular. (b) A fixed point string is a string that, when applying some function to it, the function returns the same string. Consider an Output-DFA M with the same input and output alphabet. Prove that the language: FP(M) = {w elementof sigma*: M(w) = w} is regular. (c) Suppose that instead of outputting a single character from Gamma (or epsilon) on each transition. we output a string in Gamma*. Call these machines Output*-DFAs. Prove that the languages outputted by Output-DFAs and those outputted by Output*-DFAs are the same.

Explanation / Answer

= {a, b, c}, = {0, 1} h(a)=11 h(b)=00 h(c)=0 h(bc) = h(ab) = 8 Questions about regular languages : L is a regular language. • Given L, , w , is wL? • Is L empty? • Is L infinite? • Does L1 = L2? 9 Identifying Nonregular Languages If a language L is finite, is L regular? If L is infinite, is L regular? • L1 = {anbm|n > 0,m> 0} = aabb • L2 = {anbn|n > 0} Prove that L2 = {anbn|n > 0} is ? • Proof: 10 Pumping Lemma: Let L be an infinite regular language. a constant m > 0 such that any w L with |w| m can be decomposed into three parts as w = xyz with |xy| m |y| 1 xyi z L for all i 0 11 To Use the Pumping Lemma to prove L is not regular: • Proof by Contradiction. Assume L is regular. L satisfies the pumping lemma. Choose a long string w in L, |w| m. Show that there is NO division of w into xyz (must consider all possible divisions) such that |xy| m, |y| 1 and xyi z L i 0. The pumping lemma does not hold. Contradiction! L is not regular. QED

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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