[SOLVED] R algorithm Xian Jiaotong-Liverpool University

Xian Jiaotong-Liverpool University
Module CSE203 Assignment 1
20192020 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 301019. You are also asked to print out a copy of your work and submit it in the class on 301019.
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 5tuple 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

Xian 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 as and bs}
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
xL yiffforanyzA*,eitherbothxzandyzareinLorneitheris.
MyhillNerode 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 as and bs}, is not a regular language by using Myhill-Nerode Theorem (that is, to show the number of equivalence class of
L is infinite)
15