Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
Module Code: COMP232101
Module Title: Formal Languages & Finite Automata
Use of Gen AI (Generative Artificial Intelligence) instructions:
There is a three-tier traffic light categorisation for using Gen AI in assessments.
- This assessment is red category. AI tools cannot be used.
Calculator instructions:
- You are not allowed to use any calculator in this examination.
Dictionary instructions:
- You are not allowed to use your own dictionary in this examination. A basic English dictionary is available to use: raise your hand and ask an invigilator, if you need it.
Examination Information
- There are 15 pages to this examination.
- You will have 2 hours plus your additional time allowance, if applicable, to complete this examination.
- Write your answers to each question in the allocated box below each question using a black pen. Any work outside of the provided box will not be marked.
- If you need more space for any of your answers, use the additional pages at the back of this booklet. Indicate clearly in your answer that it is continued on the additional pages.
- The boxes in the right-hand margin are for the use of the marker only.
- The total marks for each question are shown in square brackets at the end of each question.
- The number of marks available for each sub-question can be found in the margin.
- Answer all 3 questions.
- Write your name, student number and seat number in the boxes below
Question 1
A linear grammar is a context-free grammar in which the right-hand side of every production rule contains at most one variable.
(a) Consider the linear grammar G = (V, Σ, R, S), where V = {S, T}, Σ = {0, 1} and the production rules R are given below.
S → 0S | 1T | ϵ
T → 0S
What language does G generate?
(b) Show that for every regular language L there is a linear grammar G which generates L.
(c) Consider the NFA N given in the following diagram.
Construct an equivalent DFA using the power set construction.
[Question 1 Total: 13 marks]
Question 2
Consider the following context-free grammar G = (V, Σ, R, S), where V = {S, T}, Σ = {i, e} and the production rules are
S → iS | iTeS | ϵ
T → iTeT | ϵ
(a) Describe in natural language the strings generated by the grammar G.
(b) Produce a parse tree for the string iiieeeie.
(c) For two regular languages A and B we define the language A⋄B = {xy : x ∈ A and y ∈ B and |x| = |y|}. Show that A ⋄ B is context-free.
(d) Let A1, A2, and A3 be languages defined over the alphabet Σ = {a, b}, where
(i) A1 consists of all possible strings over Σ containing exactly 5 a’s and at most 13 b’s.
(ii) A2 is generated by the context-free grammar J.
(iii) A3 is recognised by a DFA M.
Prove that A1 ∩ (A3 ∪ A2) is a context-free language.
(e) Consider the following language,
L = {xy | x ∈ {a, b}
∗
, y ∈ {a, b}
∗
b{a, b}
∗
and |x| ≥ |y|}.
Prove that L is a context-free language and that L is not a regular language.
Question 3
Tick all correct answers to the questions below. Note that there may be multiple correct answers, and you need to identify all of them to be awarded points.
3.1) Select all of the following statements that are true.
out of 4
□ For every Python function there is a Turing machine which computes it.
□ For every fixed Turing machine M it is undecidable whether M halts on the empty string.
□ For any DFA M and any string w we can compute in linear time whether w is accepted by M.
□ There is a language which is accepted by a PDA with two stacks but not by a PDA with one stack.
□ There is no Turing machine which writes a symbol in every cell of the tape.
□ Every NFA with m states can be turned into an equivalent DFA with at most 2
m states.
3.2) Select all of the following statements that are true.
□ For every regular language there is a context-free grammar which generates it.
□ There are languages which are Turing decidable but not Turing recognizable.
□ The complement of every finite language is regular.
□ Every language which satisfies the pumping lemma for regular languages is regular.
□ Every language which is context-free and Turing decidable is regular.
□ The complement of every language is Turing recognizable.
3.3) Let A be a Turing recognizable language. Prove or disprove the following statement.
If A ∩ B is Turing recognizable for every Turing recognizable language B then A is Turing decidable.
You may assume, without proving it, that there exists a language which is Turing recognizable but not Turing decidable.