Question: 2. (10 points) Consider the function from {0, 1} to {a, b} given by h(0) = a, h(1) = ab. We can extend h to

2. (10 points) Consider the function from {0, 1} to {a, b} given by h(0) = a, h(1) = ab. We can extend h to operate on strings by defining h(w) = h(w1)h(w2) h(wn) where w = w1 wn and each wi {0, 1}. For example, h(010) = aaba. Extending h to languages over {0, 1}, we define h(L) = {h(w) | w L} for any L {0, 1} . Devise a general construction that, given a DFA M over the alphabet {0, 1}, builds a (DFA or NFA) M0 over the alphabet {a, b} that recognizes h(L(M)). A full proof would have three stages: setup, construction, and proof of correctness. In this exercise you will focus on the setup and construction, and then apply your construction to an example. Setup Consider an arbitrary DFA M = (Q, {0, 1}, , q0, F), and call the language of this DFA L. Construction Build a new (DFA or NFA) whose language is h(L). Application Consider the language, L, recognized by this DFA (from a previous homework):

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock blur-text-image

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!

2. (10 points) Consider the function from {0,1} to {a, b} given by h(0) = b, h(1) a. We can extend h to operate on strings by defining h(w) = h(w)h(w2) h(wn) where w-w! wn and each wi e {0, 1} For...

2. (10 points) Consider the function from {0,1} to {a, b} given by H(0) = b, h(1) = a. We can extend h to operate on strings by defining h(w) = h(wi)h(w2) ... h(wn) where w = wi ... Wn and each w; E...

2. (10 points) Consider the following DFA N over the binary alphabet, given as a transition diagram: 0 start- A B 0 1 0,1 0 1 0 D E 1 (a) Give the sequence of states (starting with A) that N goes...

PLEASE HELP!! this is a Haskell programming assignment! I've attached the given skeleton at the very bottom. Part 1. Recursive functions, higher order functions [Read Chapter 7] Problem 1. This...

2. (10 points) Consider the following frequency table of observations on the random variable X. Values 2 4 or more Observed 4 frequency Based on these 100 observations, is a Poisson distribution with...

Knowing how costs change as output changes is essential to: A. planning and controlling. B. controlling and decision making. C. planning, controlling and decision making. D. decision making and...

Spring 2016 INEN 4320: Statistical Decision Making - Midterm Exam Name:_________________________ Signature ______________________ By signing the honor pledge you are swearing that you have neither...

For all the questions below, we fix an n-dimensional Hilbert space H. For any 1-qubit gate U, we let U denote U applied to the ith qubit in a circuit. For i j we let Ci,j be the C-NOT gate whose...

1. ( points) Compute (a: lye42' dm 1 . 2. ( points) Compute / 9 (393\"2 1)3 - x/E (3; 0 . . 5:1: 3. ( pomts) Compute the integral / m dm. 1 points) Consider the function f (as) = (1 + g) . a) Using...

The Value for Money concept, simply explained, refers to the use of resources (money) to achieve organizational plans, policies and objectives (i.e. achieving Value). Value for Money (VFM) refers to...

A large department store is located in two major parts of the country: the Midwest and the Southwestern United States. The store employs 700 assistant managers. The store has organized its operations...

Diff'erences between actual costs and standard costs are found in the variance accounts of which a great number are discussed in the chapter. What considerations might determine the number of...

Problem 15-22 (LO. 2) Use the following data to calculate Chiara's 2017 AMT base. Chiara files as a single taxpayer and itemizes her deductions Taxable income Positive AMT adjustments (does not...

3 What has caused the matrix twist between CleanCo and its retail customers? CleanCo is a Polish manufacturer of cleaning products that serves the European grocery retailing market. CleanCo currently...

4 What actions are needed to straighten out the matrix twist? CleanCo is a Polish manufacturer of cleaning products that serves the European grocery retailing market. CleanCo currently segments its...

1 When IKEA was founded 60 years ago by Ingmar Kamprad, he realised that customers did not mind queuing, collecting their purchases and assembling the furniture themselves as long as the price was...