这是一篇来自英国的关于计算评估理论的作业代写，以下是作业具体内容：
- Solve the following:
Figure 1. NFA
1.1 Give the production rules of Grammar that can derive the NFA in Figure 1, if
q0=S, q1=A, q2=B, q3=C.
[ 5 marks]
1.2 In the given NFA (Figure 1), what is the resultant Regular Expression.
[3 marks]
1.3 Are the below languages context-free? If yes, draw the pushdown automata (PDA) to recognize the language, otherwise use pumping Lemma to show that the languages are non-context-free.
1.3.1 𝑳 = {𝒂 𝟒𝒏 𝒃 𝟐𝒏 𝒄 𝟐𝒏 | 𝒏 ≥ 𝟎}
[6 marks]
1.3.2 𝑳 = { 𝒂 𝒏 𝒄 𝒎 𝒃 𝟐 𝒏 𝟐𝒎 | 𝒏,𝒎 ∈ 𝑵, 𝒏 ≥ 𝒎, 𝒒 = 𝟏}
Note: 𝑛 2𝑚 is in the power of 2.
[6 marks]
- Solve the following.
2.1 Give the formal definition of the following Context free grammar (CFG):
S→A
A→aAcC | cC | aB | cA
B→ aBC | bA
C→cC | cB | cA | 𝜖
[4 marks]
2.2 Is the grammar in 2.1 ambiguous? Settle the claim using Left-hand derivation for the string 𝒂 𝒄 𝒄 𝒄 𝒄.
[5 marks]
2.3 Check if the CFG in 2.1 is in the Chomsky normal form (CNF). If not, convert it to CNF, if yes, show by comparing it with the rules of CNF.
[6 marks]
2.4 For the following grammar rules, derive its corresponding DFA/NFA and give its Language in the form of a regular expression.
S → aA | bB | cC | 𝜖
A → aA| 𝜖
B → bB | cC | 𝜖
C → bB | cC | 𝜖
[5 marks]
- Solve the following:
3.1 Construct a Turing Machine, which can solve the function 𝑓(𝑥) = 5𝑥 − 1, where
𝑥 is a unary number.
[4 marks]
3.2 Give a high-level definition and construct a Turing Machine, which can solve the function, 𝑓(𝑥, 𝑦) = 2𝑥 + 3𝑦 considering that 𝑥 and 𝑦 are a natural number and represented using unary format.
[8 marks]
3.3 Formalize your answer to 1.2 in the form of a 7-Tuple definition of Turing Machine.
[4 marks]
3.4 Derive a Turing Machine using high level description with stages to decide on the following language:
LGrammar = {<G, s> | G is a grammar that generates the DFA for checking even 1’s}
[4 marks]
- Solve the following:
4.1 Consider the following Language:
𝑳 = {< 𝑮, 𝒔, 𝒆 > | G is the undirected graph where s is the number of connected components and e is the minimum number of edges in each component.}, and
4.1.1 Draw a graph such that < 𝐺, 2, 2 > ∈ L using G1
4.1.2 For Figure 2, < 𝑮𝟏, 𝟏, 𝟏 >∉ 𝑳
4.1.3 For Figure 2, < 𝑮𝟏, 𝟏, 𝟑 > ∉ 𝑳
4.1.4 For a graph, G3, < 𝑮𝟑, 𝟏, 𝟐 >, < 𝑮𝟑, 𝟏, 𝟓 > 𝑎𝑛𝑑 < 𝑮𝟑, 𝟏, 𝟑 > are in the language L?
4.1.5 For a complete graph, please find x, if < 𝐺4, 1, 𝑥 > ∈ 𝐿, and number of vertices is twice the number of components.
[5 marks]
4.2 Consider the following Turing Machine and solve the given questions:
4.2.1 For the string 𝒃 𝒄, what is the start (initial) configuration. If start(initial) configuration is marked with C1 and it yields C2, followed by C3 and C4, then write the configuration C1, C2 and C4.
[3 marks]
4.2.2 Answer, yes or no, if the strings 𝒃 𝒄 𝒄 𝒄 are accepted by the given Turing Machine.
[2 marks]
4.2.3 Write down the computations performed by the Turing Machine for the string 𝒃 𝒃 𝒄 𝒄, and show the number of steps required to arrive at the answer.
[3 marks]
4.2.4 In the best-case, how many steps are required to reject a string?
[2 marks]
4.2.5 In the best-case, how many steps are required to accept a non-empty string?
[2 marks]
4.2.6 Write down the language of the Turing Machine in terms of regular expression it generates? (Note: its not the language it accepts, rather check for final expression)
[3 marks]
- Solve the following:
5.1 Resolve the following:
5.1.1 𝑂(𝑙𝑜𝑔3 (𝑛)) = 𝑂(𝑙𝑜𝑔5 (𝑛) True or False
5.1.2 𝑓(𝑛) = 3! 𝑛 4 is faster in asymptotic growth than 𝑔(𝑛) = 2! 𝑛 2 . True or False
5.1.3 Give the O-complexity of 𝑛 2 + 𝑛! + 1.
[3 marks]
5.2 If L1 and L2 are the languages for NFA decidable by the Turing Machines, then show that 𝐿1 ∗ ∪ 𝐿2̅̅̅are Turing decidable. (Use high-level description to settle the claims).
[4 marks]
5.3 Solve the following:
5.3.1 You are playing a shoot the balloon game at an event, where a number of balloons are coloured red, yellow, green, and blue, represented by a, b, c,and d, respectively. The balloons must be shot in the colour order specified above. However, there are certain criteria to win the game and its prize:
- Once you shoot the first red balloon, you can continue to shoot balloons of the same-colour multiple times unless you hit a balloon of the second colour, to proceed further.
- Once you hit the yellow balloon, you must now hit a balloon of a different colour, which must be hit the same number of times you hit the balloons of the first colour. Once you attain the same number of hits for the first and the third colours, you would need to hit a balloon of a different colour to proceed further. After which, no other balloons will be hit, and you can win the game.
- If you skip the first balloon colour and start with the second balloon colour,you will need to hit the fourth balloon colour next to win the game.
- You cannot start by hitting balloons of the third or fourth colour to win the game.
Now, using the rules given above, devise a PDA which can help replicate the winning
process of the balloon shooting game.
[6 marks]
5.3.2 Check if the string, 𝒂 𝒃 𝒄 𝒅, for the PDA is acceptable or not. Express your
answer using stack diagrams.
[3 marks]
5.3.3 What is the language of the final PDA in set notation?
[4 marks]