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

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.

-- 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

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

-- 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

-- 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 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.

import RunDPDA -- For testing; do not remove

3

import Hidden -- For testing; do not remove

4

5

dpdaL, dpdaR :: DPDA

6

7

dpdaL = -- Complete this

8

9

dpdaR = -- Complete this

Submissions Output

版权所有：编程辅导网 2018 All Rights Reserved 联系方式：QQ:99515681 电子信箱：99515681@qq.com

免责声明：本站部分内容从网络整理而来，只供参考！如有版权问题可联系本站删除。