12. Write an Algorithm to convert every Generalized Transition Graph (GTG) to a Transition Graph (GT) without converting to the GTG to a regular expression. Hint: Use the regular expression recursive definition.
Answer: 8 (two marks for each modes of r) We can do as the following:
•
• •
• • •
13. Using the algorithm described in the class and in the textbook that transforms a transition graph into a regular expression, eliminate state 1 in the generalized transition graph below.
Answer: 10
Find a transition that contains a regular expression r that cannot be expressed as a
string:
If it is (r), then remove the parentheses.
If the expression is r1r2, then add another state between the two states of the transition.
The first transition will be from the first state to the new one with r1. The second
transition will be from the new state to the next one with r2.
If the expression is r1+r2, then break the transition into two transitions going to the
same destination. One transition with r1 and the other one with r2.
For the r* we add a new state in between with a loop over it with r. then connect it to
the side states with null states.
Repeat these steps until no regular expression remains in the graph.
14.UsingthefirstversionofthepumbinglemmatoprovethatPRIME={ap ∣∣pisaprimenumb er} is non−regular language
Answer: 12
[Assumption (2 marks) Correct use of pumping lemma (3 marks) Show a case where the pumping lemma does not hold (5 marks) State that it is violated, and it is not a regular language (2 marks)]
Let L be the language defined by {ap} and suppose that L is regular. Then, by Theorem 13 (the pumping lemma), there would exist strings x, y, and z (where y is not the null string) such that xyiz (for all i larger than zero) are words in L. We will show that cannot be satisfied. For any selected prime number p let i = p+1 then we have:
xyiz = xyp+1z = xyz + yp
the length of this string will be p + p [length y] which is p (1 + length y). The length is divisible by two elements and is not a prime number anymore. Hence xyiz is not in the language. Our assumption was wrong as the pumping lemma is violated. Therefore, the language is not regular.