1. Describe in words or give a regular expression for the language accepted by the transition graph TG (i) pictured on the last page of this assignment.
Answer: 10
b (¦« + aa + a*b) or equivalents
2. Let¡Æ= {a,b} .Consider the language L over ¡Æ that contains empty string and all words whose length is divisible by 6. Build a transition graph that accepts L.
Answer: 10
3. Let L be any language. We define L¡¯ = {reverse(x)|x in L}. (For example, if L = {b, baa, aaabb, aabba}, then L¡¯ = {b, aab, bbaaa, abbaa}.
(a) Prove that for any language L, if there is an FA that accepts L, then there is a TG that accepts L¡¯.
Answer: 5
(b) Prove that for any language L, if there is a TG that accepts L, then there is a TG that accepts L¡¯.
Answer: 5
If we have an FA that accepts L then there is a path from the initial state to one of the final states for the words in this language. We can do the following steps. First, reverse all the directions of the links in the automaton. Then add a new state as a new initial state and link it to all final states in FA using the null string (or simply change all final states into initial states). Change all old final states into normal states. Also make the old initial state the new final state. As a result, we have a TG which accepts the reverse of L.
Same as previous part if we have a TG that accepts L then there is a path for each word in the language from the initial state to one of the final states. First, reverse all the directions of the links. Then add a new state as a new initial state and link it to all final states in TG using the null string. Change all old final states into normal states. Also make the old initial state the new final state. As a result, we have a TG which accepts the reverse of L.
4. Using the bypass algorithm in the proof of Kleene¡¯s Theorem (Theorem 6 in the textbook), Lemma 2, convert TG (ii) pictured on the last page of this assignment into a regular expression.
Answer: 10
For simplicity x= a + b(¦«+ ab*a)b
answer: (xb)* (xa)(a+ba)* [bb (xb)* (xa) (a+ba)*]* or all its equivalent.
5. Consider FA (iii) and FA (iv) on the last page of this assignment. Let L3 be the language accepted by FA (iii), and let L4 be the language accepted by FA (iv).
(a) Using the algorithm of Kleene¡¯s theorem, Lemma 3, Rule 2, construct an FA for the union language L3 + L4.
Answer:7
(b) Give an example of a word in the language L3+L4 that is also in both languages L3 and L4.
Answer: 1
¡®aaaa¡¯ or ¡®aaa¡¯
(c) Give a word in the language L3 + L4 that is also in L3, but not in L4.
Answer: 1
¡®bbb¡¯ or ¡®abb¡¯
(d) Give a word in the language L3 + L4 that is also in L4, but not in L3. Answer: 1
¡®a¡¯
6. Let L4 be the language accepted by FA (iv) on the last page of this assignment.
(a) Using the algorithm of Kleene¡¯s theorem, Lemma 3, Rule 3, construct an FA for the product language L4L4. Hint: make two copies of the FA and give different names to the states in each one.
Answer: 8
(b) Describe (in English phrases) the language L4L4 (the language accepted by your answer to part (a)).
Answer: 2
all string over alphabet {a,b} that has at least two a¡¯s and end in ¡®a¡¯
7. Let L3 be the language accepted by FA (iii) on the last page of this assignment.
(a) Using the algorithm of Kleene¡¯s theorem, Lemma 3, Rule 4, construct an FA for the
language L3*
Answer: 8
(b) Is the language L 3 the same as the language L 3 * ? If so, justify your answer with a brief explanation. If not, give an example of a word that is in one language, but not the other.
Answer: 2
the only difference is null string as the language is all words containing substrings such as ¡®ab¡¯,¡¯aaa¡¯, or ¡®bbaa¡¯. L* contains all those words in addition to null string.
8. Consider NFA (v) on the last page of this assignment. Convert this NFA into an FA.
Answer: 10