11/9/2020 Grok | COMP30026 Practice Exam
Ques on 7
Ques on 7 Part C (6 mark)
Recall the reverse opera on on languages (over alphabet ), defined as follows:
In words, is the language of all strings appearing backwards in . As an example, if is then is .
Part C (6 marks)
In Assessed Worksheet 4, you proved that the class of regular languages is closed under the reverse opera on by showing how we can transform a DFA for into an NFA for .
In this ques on, you will prove this result again, but by using regular expressions.
Hint: Think of a recursive rela onship that captures the reversal transforma on which you carried out in parts A and B.
Instruc ons
WriteaHaskellfunc onreverseRE :: RegExp -> RegExpwhichtakesanarbitrary regular expression a language and returns a regular expression for the language
Your regular expressions do not need to be simplified, they only need to be correct. Format
RegExp.hs provides a regular expression type RegExp, and a parser for regular expressions,parseRE :: String -> RegExp.Usethistypetoenteryouranswer.
For example:
The regular expression may be entered as follows:
Star (Concat (Symbol ‘b’) (Symbol ‘a’)),or
parseRE “(ba)*”.
The regular expression may be entered as follows:
Concat (Symbol ‘a’) (Union EmptyStr (Concat (Symbol ‘a’) (Symbol ‘b’))),or
parseRE “a(eps | ab)”.
.
https://groklearning.com/learn/unimelb-comp30026-2020-s2/prac-exam/19/
1/1
Cheng
RL L
L
RL
)ba ∪ ε(a
}110 ,10 ,0{ RL
L RL
.}i lla rof Σ ∈ ix ,L ∈ nx ⋯ 1x0x | 0x1x ⋯ nx{ = RL Σ
∗)ab(
}011 ,01 ,0{ L