Ask Question, Ask an Expert

+61-413 786 465

info@mywordsolution.com

Ask Automata & Computation Expert

Models of Computation Assignment -

Purpose - To improve and consolidate your understanding of regular and context-free languages, finite-state and pushdown automata. To develop skills in analysis and formal reasoning about complex concepts, and to practise writing down formal arguments.

Challenge 1 - This challenge is to design eight finite relations and submit them via Grok. Let D = {1, 2, 3}. We can think of a binary relation on D as a subset of D × D. For example, the identity relation is {(1, 1),(2, 2),(3, 3)}. There are 9 elements in D×D, so there are 29 = 512 different binary relations on D.

Construct eight of these, r0, . . . , r7, satisfying the criteria given in the table below. Each relation should be presented as a Haskell list of pairs, that is, an expression of type [(Int, Int)]. For full marks, each relation has to be as small as it can be.

 

Reflexive

Symmetric

Transitive

r0

no

no

no

r1

no

no

yes

r2

no

yes

no

r3

no

yes

Yes

r4

yes

no

no

r5

yes

no

Yes

r6

yes

yes

no

r7

yes

yes

Yes

Challenge 2 - This challenge is to design three DFAs and a regular expression and submit them via Grok. An expression such as (01 ∪ 1)* ∩ (0*11)* is not a regular expression, since ∩ is not a regular operation. Nevertheless, the expression denotes a regular language.

a. Give a 3-state DFA Da for (01 ∪ 1)*.

b. Give a 4-state DFA Db for (0∗11)*.

c. In tute exercise 61 we constructed "product" automata for the intersection of languages. Now find a minimal DFA Dc for (01 ∪ 1)* ∩ (0∗11)*. You can build the DFA that is the "product" of Da and Db, but be aware that the result may not be minimal, so you may have to apply minimisation.

d. Use the NFA-to-regular-expression translation shown in Lecture 12, to turn Dc into a regular expression r for (01 ∪ 1)* ∩ (0*11)*.

Challenge 3 - This challenge is to complete, on Grok, some Haskell functions that will allow us to test for membership of languages given as regular expressions. You have probably used regular expression features in your favourite programming language, and this challenge will help you understand how such features are implemented.

Let us call a language A volatile iff ε ∈ A. For example, L(10 ∪ (11)*) is volatile, but L((0 ∪ 1)(11)*) is not. Another useful concept is that of a derivative of a language with respect to a (finite) string. The derivative of A with respect to s,

d(A, s) = {w | sw ∈ A}

For example, if A = {0, 02, 102, 111, 1102} then d(A, 11) = {1, 02}. For another example, if B is the language given by the regular expression (00)* then d(B, 0) = L((00)*0) = L(0(00)*).

We can extend the definition of "volatile" to regular expressions r: We say that r is volatile iff ε ∈ L(r). Similarly we extend d so that the function takes, and produces, regular expressions. Let us first handle the case where the string s is of length 1, that is, s is a single symbol x. We define

d1(∈, x) = ∅

d1(∅, x) = ∅

d1(y, x) = ∅ if y is a symbol and y ≠ x

d1(x, x) = ∈

d1(r1 ∪ r2, x) = d1(r1, x) ∪ d1(r2, x)

d1(r1 r2, x) = d1(r1, x) r2 ∪ d1(r2, x) if r1 is volatile

d1(r1 r2, x) = d1(r1, x) r2 if r1 is not volatile

d1(r*, x) = d1(r, x) r*

Now we can define the general case, that is, the derivative of r with respect to an arbitrary string s. We define d(r, ∈) = r and, for k ≥ 1: d(r, x1x2 · · · xk) = d1((. . . d1(d1(r, x1), x2), . . .), xk)

You should think about why the above recursive definitions are correct, before you complete their Haskell implementations on Grok. On Grok you will find a Haskell type RegExp for regular expressions.

a. Write a Haskell function volatile :: RegExp -> Bool that determines whether a regular expression is volatile.

b. Complete a Haskell function derivative :: RegExp -> String -> RegExp so that you can use Haskell to calculate derivatives of regular expressions.

c. Write a function contains :: RegExp -> String -> Bool which takes a regular expression r and a string w and decides whether w ∈ L(r). This function must use the functions volatile and derivative.

Challenge 4 - Let Σ be a finite non-empty alphabet and let x ∈ Σ be a symbol. For every w ∈ Σ* and x ∈ Σ, let omit(x, w) be the string w with all occurrences of x removed. For example, if Σ = {a, b, c} and w = baabca then omit(a, w) = bbc. Similarly, omit(b, bb) = ∈.

We now "lift" this function to languages: To "drop" a symbol from a language L will mean to "omit" it from every string in L. That is, for L ⊆ Σ*, define

drop(x, L) = {omit(x, w) | w ∈ L}.

For example, if L = {aa, baabca, bbaac, bbc} then drop(a, L) = {∈, bbc} and drop(b, L) = {aa, aac, aaca, c}.

a. Show that if R is a regular language then drop(a, R) is a regular language.

b. Assuming {a, b} ⊆ Σ, provide a language L such that drop(a, L) is context-free and non-regular, while drop(b, L) is regular.

Challenge 5 - Every regular language can be recognised by a push-down automaton which has only three states, qI , qR, and qA. Show in detail how to systematically translate an arbitrary DFA to a PDA with only three states. Try to answer this question precisely, that is, make use of the formal definitions of DFAs and PDAs. So, given an arbitrary DFA (Q, Σ, δ, q0, F), define precisely each component of the corresponding PDA (Q′, Σ′, Γ, δ′, q′0, F′).

Hints: (a) A PDA does not have to have an empty stack in order to accept a string; (b) its stack alphabet Γ can be whatever (finite) set of symbols you choose; and (c) we named the states qI, qR, and qA for a reason.

Challenge 6 - Let us fix the alphabet Σ = {0, 1}. Define a substring of w ∈ Σ* to be any string x ∈ Σ* such that w = uxv for some u, v ∈ Σ*. Now consider the language

A = {w ∈ Σ*| 001 is not a substring of w}

For example, ∈, 01, 1111, 10101, and 0111010101 are in A, but 10001 and 11001011 are not.

Consider the context-free grammar G = ({S}, Σ, R, S), where the rules R are: S → ∈

| S 0

| 1 S

| 0 1 S

Show that L(G) = A.

Hint: Show L(G) ⊆ A using structural induction and show A ⊆ L(G) by induction on the length of strings in A.

Attachment:- Assignment File.rar

Automata & Computation, Computer Science

  • Category:- Automata & Computation
  • Reference No.:- M93114691
  • Price:- $70

Priced at Now at $70, Verified Solution

Have any Question? 


Related Questions in Automata & Computation

Models of computation assignment -purpose - to improve and

Models of Computation Assignment - Purpose - To improve and consolidate your understanding of regular and context-free languages, finite-state and pushdown automata. To develop skills in analysis and formal reasoning abo ...

Iot and data analytics1 analyse the taskanalyse what is

IOT and data analytics 1. Analyse the Task Analyse what is expected of you. This includes careful reading of the assignment task as specified in the Subject Outline. The executive summary of the research project is to be ...

Prove or disprove the following proposed inference rules

Prove or disprove the following proposed inference rules for functional dependencies. A proof should be made by using the reflexive, augmentation, transitive, decomposition, union, and pseudotransitive rules. A disproof ...

Question 1a digital computer has a memory unit with 16 bits

Question 1: A digital computer has a memory unit with 16 bits per word. The instruction set consists of 122 different operations. All instructions have an operation code part (opcode) and an address part (allowing for on ...

Question - design a state machine that will control a

Question - Design a state machine that will control a vending machine. The vending machine has 4 inputs, N, D indicating a nickel or dime was inserted as well as clk and an active high asynchronous reset. The vending mac ...

Solve the question given belowprove the following statement

Solve the question given below Prove the following statement using Hall's Theorem. For any bipartite graph G=(U, V, E), if every node (either a left node or a right node) has exactly d neighbors, where d is an arbitrary ...

Regular expressions automatacomputabilitytheory of

Regular expressions, automata/computability/theory of computation How would I go about interpreting regular expressions? For example, how would I interpret the following in English: (0+1)*011 0*1*2* 0^(+)1^(+)2^(+)

Prove or disprove the following proposed inference rules

Prove or disprove the following proposed inference rules for functional dependencies. A proof should be made by using the reflexive, augmentation, transitive, decomposition, union, and pseudotransitive rules. A disproof ...

Question 1hoare logic semantics for each of the parts below

Question 1 Hoare Logic Semantics For each of the parts below, justify your answer briefly. 1. For which programs S does {False} S {True} hold? 2. For which programs S does {True} S {False} hold? 3. For which programs S d ...

Models of computation assignment -purpose - to improve and

Models of Computation Assignment - Purpose - To improve and consolidate your understanding of regular and context-free languages, finite-state and pushdown automata. To develop skills in analysis and formal reasoning abo ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

Why might a bank avoid the use of interest rate swaps even

Why might a bank avoid the use of interest rate swaps, even when the institution is exposed to significant interest rate

Describe the difference between zero coupon bonds and

Describe the difference between zero coupon bonds and coupon bonds. Under what conditions will a coupon bond sell at a p

Compute the present value of an annuity of 880 per year

Compute the present value of an annuity of $ 880 per year for 16 years, given a discount rate of 6 percent per annum. As

Compute the present value of an 1150 payment made in ten

Compute the present value of an $1,150 payment made in ten years when the discount rate is 12 percent. (Do not round int

Compute the present value of an annuity of 699 per year

Compute the present value of an annuity of $ 699 per year for 19 years, given a discount rate of 6 percent per annum. As