Theory of Computation Assignment l 1) Let Li-peach, apple, cherry and L2-pie, co

Question

Theory of Computation Assignment l 1) Let Li-peach, apple, cherry and L2-pie, cobbler, ). List the elements of LiL2 in lexicographically enumerated order. 2) For each of the following languages L, give a simple English description. Show two strings that are in L and two that are not (unless there are fewer than two strings in L or two not in L, in which case show as many as possible). a) L- !w e {a, bi exactly one prefix of w ends with a) b) L- (w e a, b* : all prefixes of w ends with a) 3) For each of the following statements, state whether it is True or False. Prove your answer a) VLi, L2 (Li L2 iff L L2*) (Hint: Try to find counterexample) b) Every infinite language is the complement of a finite language. (Hint: Try to find counterexample) d) VLI, L2, (Li L2)-L*L2 (Hint: Try to find a counterexample) e) VLl, L2 ((Li U L2)" = Li * L:"). (Hint: Try to find a counterexample) f) ''Li, L2,L3 ((Li L2) L,-(L, u L3) (L2 L3)). (Hint: Try to find a counterexample) g) VL ((LL(Hint: Consider definition of L) 4) Let -0,13, how many strings are there in the following languages b) 2

Explanation / Answer

1.

L1={peach,apple,cherry}

L2={pie,cobbler,epsilon}

L1L2 in lexicographycally order (with shortest first within a fixed length then alphabetically) is:

{apple,peach,cherry,applepie,peachpie,cherrypie,applecobbler,peachcobbler,cheerycobbler}

2.

a)

Example of two strings in L={ab,abb}

Example of two strings not in L={aab,aabb}

b)

Example of two strings in L={aa,aaa}

Example of two strings not in L={abb,abbb}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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