[SOLVED] 代写 R algorithm Xi’an Jiaotong-Liverpool University

Xi’an Jiaotong-Liverpool University
Module CSE203 Assignment 1
2019‐2020 Semester 1
(The tasks contribute 10% to the overall assessment of CSE203)
Submission
Please complete the assessment tasks using Microsoft Word and submit via ICE by 30‐10‐19. You are also asked to print out a copy of your work and submit it in the class on 30‐10‐19.
Tasks
1
Design a deterministic finite automaton to accept the set of binary strings that, when interpreted as an integer, is divisible by 3. Note that the most significant digit is the first to be read.
a)
Give the 5‐tuple notation for your automaton, with the transition function expressed as a table. Then, draw the transition diagram for your DFA.
10
b)
Draw the transition diagram for your DFA.
5
2
Consider the language L of all strings over {a,b} whose 2rd symbol from right end is an a.
a)
Write regular expressions for the languages L.
5
b)
Use the construction outlined in class and the course note to convert the regular expression in a) to an equivalent NFA by diagram
5
c)
Use the subset construction to find an equivalent DFA
5
d)
Minimize the DFA in c)
10
3
Let R and S be any regular expressions. Prove (R+S)*=(S*R*)*.
10

Xi’an Jiaotong-Liverpool University
4
Using the algorithm outlined in the lecture to convert the DFA M below to its equivalent regular expression.
15
1
a ba
2
3
a
5
Let L={ w ∈ {a, b}*: w has equal number of a’s and b’s}
a)
Using the Pumping Lemma to prove L is not a regular language.
10
b)
Using closure property to show L is not a regular language.
10
6
Given a language L over an alphabet A, let the ≈L be the equivalence relation over A* defined as
x≈L yiffforanyz∈A*,eitherbothxzandyzareinLorneitheris.
Myhill‐Nerode Theorem says, L is regular if and only if the number of equivalence class
of ≈L is finite.
Show that L={ w ∈ {a, b}*: w has equal number of a’s and b’s}, is not a regular language by using Myhill-Nerode Theorem (that is, to show the number of equivalence class of
≈L is infinite)
15