C++编程讲解、辅导Algorithms留学生编程、讲解c/c++程序语言
辅导留学生 Statistics统计、回归、迭代|讲解R语言编程
2 Challenge description
Consider the languages A1=(a(bb)∗)∗, A2=((ab)∗b)∗, and A3=A1∩A2 over the alphabet {a,b}.
Your task is to design three DFAs:
1.Construct a complete and minimal DFA for A1.
2.Construct a complete and minimal DFA for A2.
3.Construct a complete and minimal DFA for A3.
Submission instructions
Submit your DFAs for parts 1, 2 and 3 as Haskell expressions of type DFA (named dfa1, dfa2, and dfa3 respectively).
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 find useful.
Note:
Recall the DFA representation format from Assessed Worksheets 3 and 4. For example, let's say we want to represent the following DFA:
This DFA could be represented in Haskell as follows:
dfa = ([1,2], "ab", t, 1, [2])
where
t = [ ((1,'a'),2)
, ((1,'b'),1)
, ((2,'a'),1)
, ((2,'b'),2)
]
Your DFAs' transition functions should be total.
Marking guide
Each correct but not minimal DFA is worth 1/3 marks. Each correct minimal DFA is worth 2/3 marks. The maximum marks for this problem is 2. Note that the results of correctness and minimality tests will not be visible after the submission.
-- we provide the same files as in assessed worksheet 4
2
import DFA
3
import NFA
4
import VisDFA
5
-- we provide solutions to worksheet 4 problems, you may find useful
6
import HiddenAlgorithms (productDFA, determiniseNFA, minimiseDFA)
7
-- one more module is required for testing purposes
8
import Hidden
dfa1, dfa2, dfa3 :: DFA
-- TODO: put your definitions here
13
dfa1 = ([1,2], "ab", t, 1, [1])
3 Challenge description
Construct the language-transformer function skip defined as follows: skip(L)={xy∣xzy∈L, and x,y∈Σ∗,z∈Σ}, where L is a regular language. Language skip(L) contains all strings obtained from the strings of L by removing any symbol.
For example:
if L={ϵ,ab}, then skip(L)={a,b};
if L={a,b}, then skip(L)={ϵ}.
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 skip 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 find useful.
Note: Your function does notneed to return complete or minimal DFAs, but it should always return OK DFAs (according to checkDFA defined in DFA.hs).
Note:
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
Correct skip 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.
Challenge 3: Let's do some skipping!
Main.hs
DFA.hs
NFA.hs
VisDFA.hs
1
-- provide the same files as in assessed worksheet 4
2
import DFAp
3
import NFA
4
import VisDFA
5
-- we provide solutions to worksheet 4 problems, you may find useful
6
import HiddenAlgorithms (determiniseNFA, minimiseDFA)
7
-- one more module is required for testing purposes
8
import Hidden
9
10
-- TODO: Complete this function
11
skip :: DFA -> DFA
12
skip dfa
13
= dfa
14
Submissions Output
4 Challenge description
Note:
If the equations in the following specification do not render properly, please save your work and refresh the page.
4 Challenge description
In this challenge, you will show that finite state automata can compute propositional logic expressions. You will implement two DFA construction algorithms on the alphabet Σ={f,t}; one for each of the following parametrised families of regular languages:
1.Ti={w0w1⋯wn | n≥i, wi=t, and for j≠i, wj∈Σ}where i∈{0,1,…}.
That is, Ti contains all strings over alphabet Σ={f,t} with a symbol in position i (counting from 0) equal to t. For example:
T0={t––,t––f,t––t,t––ff,t––ft,t––tf,t––tt,…}={t}∘Σ∗,
T1={ft––,tt––,ft––f,ft––t,tt––f,tt––t,…}=Σ∘{t}∘Σ∗.
2.Mφ={w=w0w1⋯wn | wj∈Σ and θw⊨φ}where φ is a propositional formula with variables V0,V1,…, and θw={V0↦w0,V1↦w1,…,Vn↦wn,Vn+1↦f,…}is a truth assignment to the first n+1 of those variables (other variables are assigned false).
That is, Mφ is the set of all the truth assignments (encoded as strings) that make the formula φ true. For example:
MV0⇒V1={ϵ,f,ff,ft,tt,fff,fft,ftf,ftt,ttf,ttt,…},M(V0⊕V1)∧(V1⇔V2)={ftt,t,tf,tff,fttf,fttt,…}.
We provide more examples of the languages in these families in the video below.
Video breakdown of challenge 4 definitions and task; 26MB, download.
Submission instructions
You will implement, in Haskell, DFA constructions for each of these parametrised language families. You must submit two Haskell functions:
ithIsTrue :: Int ->DFA, which takes a non-negative integer i as input and returns a DFA for Ti.
models :: GExp Int ->DFA, which takes a formula exp (with non-negative integer variable names) as input, and returns a DFA recognising Mexp.
You may use any of the helper functions from DFA.hs and NFA.hs, and the visualisation module VisDFA.hs.HiddenAlgorithms.hs also makes available completed solutions to the problems of Assessed Worksheet 4, including productDFA and complementDFA, which you may find useful. See Assessed Worksheet 4 for more details on the types and functions available from these modules.
Note: Your functions do not need to return complete or minimal DFAs, but they should always return OK DFAs (according to checkDFA defined in DFA.hs).
Hints:
We recommend starting with part 1—implementing ithIsTrue—since we expect that this function will be very helpful for part 2.
Part 2 may seem particularly daunting. However, a solution does not need to involve a lot of code. Once you understand the meaning of Mφ, there are several ways to approach the implementation. One involves a recursive algorithm based on the following observations:
oMφ∧ψ=Mφ∩Mψ,
oM¬φ=(Mφ)c, and
oAll propositional connectives can be expressed in terms of NOT and AND.
After reflecting on these observations, consider the following questions:
oWhat is MVi?
oWhat is Mt?
oWhat is Mf?
Marking guide
The visible tests check that you have defined the two required functions. Invisibly, we will test each of your two functions on multiple input parameters, unknown to you. Marks will be allocated based on the proportion of tests passed, with 1.0 marks available from tests of ithIsTrue, and 1.0 marks available from tests of models (which may indirectly test the correctness of ithIsTrue).
Lihang
1
-- we provide the same files as in assessed worksheet 4
2
import DFA
3
import NFA
4
import VisDFA
5
-- along with the generalised expression type from assignment 1
6
import Exp
7
-- we provide solutions to worksheet 4 problems, you may find useful
8
import HiddenAlgorithms (productDFA, complementDFA)
9
-- one more module is required for testing purposes
10
import Hidden
-- TODO: Implement this function
14
ithIsTrue :: Int -> DFA
15
ithIsTrue i
-- TODO: Implement this function
5 Challenge description
Consider these three context-free grammars over alphabet Σ={a,b}:
1.A=({S,T},Σ,RA,S)whereRA:S→a T∣S b∣ϵT→S b∣b
2.B=({S},Σ,RB,S)whereRB:S→ϵ∣a S b∣a S b b
3.C=({S,T},Σ,RC,S)whereRC:S→T∣a S b bT→ϵ∣a T b
The task is to identify any ambiguity in these grammars, and to determine how the corresponding languages are related. More specifically:
1.Determine whether A is ambiguous, and if it is, provide a string in L(A)which has two different parse trees.
2.Determine whether B is ambiguous, and if it is, provide a string in L(B)which has two different parse trees.
3.Determine whether C is ambiguous, and if it is, provide a string in L(C)which has two different parse trees.
4.Specify the sublanguage relation on {A,B,C}. That is, for each (X,Y) pair of grammars from the set {A,B,C}, determine whether L(X)⊆L(Y).
Here L(X) denotes the language generated by grammar X.
Submission instructions
For the first three parts, submit your answer by defining part1, part2, and part3. Each answer should be of type Answer as defined in the code box:
1.If you find that a grammar is ambiguous, your answer should be of form Ambiguous s, where s∈Σ∗is a string that has different parse trees. The string Sshould be of Haskell's type String and only contain as and bs, as in the example "abba".
2.If you find that a grammar is unambiguous, your answer should be of the form Unambiguous. You do not need to include a justification for your answer in this case.
For part 4, submit your answer by defining part4, a Haskell expression of type [(Grammar,Grammar)]. This is a list representing the sublanguage relation on {A,B,C}. That is, you should list all the cases (X,Y), such that L(X)⊆L(Y).
The sublanguage relation is of course reflexive, that is, we have L(A)⊆L(A), L(B)⊆L(B), and L(C)⊆L(C). We have already included these three cases in the stub for part4.
Marking guide
Each of the four parts is worth 0.5 marks. The question is auto-marked, so no fractions of 0.5 will be awarded. That is, each part has to be completely correct, to attract the 0.5 marks.
Remember that if Grok responds to your submission with "Your submission passed our tests", that only means your variables part1–part4 are well-typed; it says nothing about correctness, which we test later.
Challenge 5: In grammar school
Challenge 6: Let's do some push-downs!
Challenge description
A deterministic pushdown automaton (DPDA) is a pushdown automaton that never finds itself in a position where it can make two different transition steps. That is, from any configuration (state, input symbol, stack symbol), there is at most one state it can transition to. (If it is in a configuration where no state can be transitioned to, the DPDA immediately rejects its input.) Each transition step consumes exactly one input symbol. The stack operations are exactly as for PDAs: in one transition step, the DPDA can push to the stack, pop from the stack, do both, or leave the stack unchanged. We follow the conventions for PDA transitions, as used in lectures, that is, in stack operations we use epsilon (ϵ) to mean 'nothing'. So 'pop x' is captured as 'replace x by ϵ', 'push x' as 'replace ϵ by x', and 'leave the stack untouched' by 'replace ϵ by ϵ'.
Your task is to construct two DPDAs, both having input alphabet {a,b,c}. The DPDAs should recognise the following languages:
4.The language L={xcxRy∣x∈{a,b}∗,y∈{a,b,c}∗}.
Note: For a string x, xRdenote the reverse of x. For example, the reverse of babbb is bbbab.
Here are some examples of strings in L: c, cab, and bacaba. The following are not in L: abba and acbac.
5.The language R={aibjck∣i≥0,j≥0,k≥0,i+j+k is even}.
Here are some examples of strings in R: ϵ, aa, and accc. The following are not in R: acc and bcbc.
You should try to be economic with the number of states (see the marking guide below).
Submission instructions
You will submit two DPDAs, in the form of Haskell expressions of type DPDA.
5.dpdaL recognising language L.
6.dpdaR recognising language R.
You can find the type definition in the file DPDA.hs, where the constant eps is also defined.
Note:
The way we represent DPDAs is not unlike what we did for DFAs. For example, we represent the following DPDA:
in Haskell as follows:
dpda
= ([1,2,3,4], "01", "0$", delta, 1, [1,4])
where
delta = [ ((1,'0',eps), (2,'$'))
, ((2,'0',eps), (2,'0'))
, ((2,'1','0'), (3,eps))
, ((3,'1','0'), (3,eps))
, ((3,'1','$'), (4,'$'))
]
Marking guide
Each part is worth 1 mark.
3.Part 1 will attract 0.5 marks for a correct DPDA dpdaL, and an additional 0.5 marks for one that has no more than 4 states.
4.Part 2 will attract 0.5 marks for a correct DPDA dpdaR, and an additional 0.5 marks for one that has no more than 3 states.
Lihang
Challenge 6: Let's do some push-downs!
Main.hs
DPDA.hs
import DPDA
2
import RunDPDA -- For testing; do not remove
3
import Hidden -- For testing; do not remove
dpdaL, dpdaR :: DPDA
dpdaL = -- Complete this
dpdaR = -- Complete this
Submissions Output