1. Using any of the methods described in Chapter11, determine if the two finite automata below accept the same language or not. (Show your work)
Answer: (10 marks)
making either L1’ or L2’ (2 marks), making either (L1’ + L2) or (L2’ + L1) (2 marks), making either (L1’ + L2)’ or (L2’ + L1)’ : (2 marks), using any of the 3 methods to show the part is not empty (2 marks), for explaining the conditions and conclude they are not the same (2 marks)
The two languages L1 and L 2 are equivalent if and only if the following language is empty: (L1ÇL2’) + (L2ÇL1’) = (L1’ + L2)’ + (L2’ + L1)’
The languages:
Making (L1 + L2’):
Making (L1 + L2’)’:
As this part is not empty (by using the second method making the start state blue then read an ‘a’ and make the final state blue) then the total expression is not empty. As a result, these two languages are not equivalent.
2. Define a decision procedure that given 2 FAs will determine if there exist any words that are not accepted by either one.
Answer: 10 marks
Construct the FA for (L1’ÇL2’) = ( L1 + L2)’ which is an FA that accepts words that are not accepted by either original FAs. Then using one of the methods explained in the lecture such as blue method check if the language of this FA is empty or not. If empty, it means there are no words. Otherwise, there exist at least one word that is not accepted either one.
3. Describe the language generated by the following context free grammar (CFG) (L=Lambda) :
S→VW | XY V→aV b | L W→cW | L
X→aX | L Y→bY c | Z Z→bZ | L
Answer: 10 marks (any equivalent description)
{ax by cz |x=yory>=z,x>=0,y>=0,z>=0}orwecanshowitlikethisaswell:
{ an bn cd |n>=0,d>=0}or{aj bk cL |k>=L,j>=0,k>=0,L>=0 }
4. Show that the CFG above (in Question 4) is ambiguous by finding a word with two distinct syntax trees. Show both syntax trees.
Answer : 10 marks (2 marks: correct choice of a word, 4: marks each tree.)