11/9/2020 Grok | COMP30026 Practice Exam
Ques on 6
Ques on 6 Part B (2 marks)
We define the simplicity of a regular expression as the total number of occurrences of concatena ons, unions, Kleene stars, alphabet symbols, empty string symbols, and empty set symbols in the regular expression. The simplest regular expression for a regular language is the regular expression with the smallest possible simplicity expressing that language.
For example, the regular expression has two concatena ons, one union, one Kleene star, one empty string symbol, and three alphabet symbols, for a total
simplicity of 8. However, it is not the simplest possible regular expression for its language; expresses the same language, and has simplicity 6.
Part B (2 marks)
Consider this NFA , with alphabet :
What is the simplest regular expression for
Note: Par al marks will be awarded for a regular expression which is correct but not
the simplest.
Hint: This task does not require you to apply that the algorithm for construc ng regular expressions from NFAs. Moreover, this algorithm usually produces overcomplicated regular expressions. Instead, you should try to understand the language of the NFA and build a simple regular expression directly.
Instruc ons
Giveyouranswerasaregularexpressionr6B :: RegExp. Ft
https://groklearning.com/learn/unimelb-comp30026-2020-s2/prac-exam/15/ 1/1
, the language recognised by ?
Cheng
N )N(L
}b,a{ N
∗)aba ∪ ε(
∗)aba(