Challenge description
Construct the language-transformer function slice defined as
Zw’ € L, where w is w’ with
every second symbol removed
Copyright By PowCoder代写 加微信 powcoder
where L is a regular language. Language slice(L) contains all
strings obtained from the strings of L by removing every second
For example:
if I = {a, ab, bc, abed}, then slice(L) = {a, b, ac}i
if I = {a, aa}, then slice(L) = {a}.
Hint: Construct an NFA that contains two layers represented by
copies of the initial DFA that recognises L. Connect the layers
(think about the meaning of these layers, how the layers should be
connected, and how the accept states of the NFA should be
defined). Then, determinize the NFA.
Submission instructions
Submit your language-transformer as a Haskell function slice that
implements a DFA to DFA conversion.
You may use any of the utility functions from DFA.hs, NFA.hs, or
VisDFA.hs. Moreover, HiddenAlgorithms.hs exports solutions to
the problems of Assessed Worksheet 4, including productDFA,
minimiseDFA, and determiniseNFA, some of which you may finc
useful. You can find a full listing of all exported functions by typing
:browse HiddenAlgorithms into GHCi.
Note: Your function does not need to return complete or minimal
DFAs, but it should always return OK DFAs (according to checkDFA
defined in DFA.hs).
Because of the determinisation step, your function may be slow
for moderately-sized input DFAs. We will test your solution only
with DFAs of up to 4 states.
Marking guide
A correct slice function is worth 2 marks. We will test your
function on 8 input DFAs, and your mark will be n/ 4, where n is the
number of correct output DFAs. The result of only the first of these
test cases will be visible to you.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com