Ask Question, Ask an Expert

+1-415-315-9853

info@mywordsolution.com

Ask Computer Engineering Expert

1. Let  ∑ ={f0,1}, and let A be the language {abwba| a,b Ε ∑ , w Ε ∑*}. Construct a DFA that accepts precisely strings in A.

2. Convert the following NFA into an equivalent DFA.

1177_NFA.jpg

3. (Floyd & Beigel) You and an opponent are seated at a table, and on the table is a square board. At each of the four corners of the board, there is a disc, each one red on one side and black on the other. You are blindfolded, and thus cannot see the con guration of the discs, but you claim that you can ip the discs such that they are all facing with the same color up. On each move, you can ip either one or two discs (either adjacent or diagonal to each other). If this results in a winning state, your opponent must announce that. Otherwise, your opponent may choose to rotate the board 0° , 90° , 180° , or 270° .

Find the shortest sequence of moves that is guaranteed to win the game, no matter what rotations of the board are made. Be sure to include a proof that your solution is correct and that it is the shortest possible.

4. For a language A over an alphabet ∑, define the complement of A, A‾ = {x|x Ε≠ A}. Prove that the class of regular languages is closed under complementation.
5. For a string w = w1w2.....wn, define the reverse of w, wR = wn.....w2w1. For a language A, define AR= {wR |wΕA}. Show that, if A is regular, then so is AR.

6. For languages A and B, let the shu e of A and B be the language

{w|w = a1b1 .....akbk; where a1.....ak Ε A and b1......bk Ε B; with each ai,bi Ε ∑*} Prove that the class of regular languages is closed under shuffe.

7. Define a 2165_for all.jpgFA to be a 5-tuple M = (Q, ∑, δ,q0, F), where δ : QX∑u{Ε}→P(Q) is defined as for a NFA. As a dual notion to nondeterministic acceptance, we say that M accepts x Ε ∑* if every possible state of M after reading x is an accepting state. Prove that a language is regular if and only if it is recognized by a 2165_for all.jpgFA.

8. Let M be a NFA with k states.

(a) Prove that, if L(M) ≠ ø;, then L(M) contains a string of length at most k (HINT: Think about the possibilities for path length in M, keeping in mind the Pigeonhole Principle.)

(b) Show that, even if L(M)‾ ≠ ø ;, it is not necessarily the case that L(M)‾ has a string of length at most k.

Computer Engineering, Engineering

  • Category:- Computer Engineering
  • Reference No.:- M91327

Have any Question? 


Related Questions in Computer Engineering

A searching method that uses linear interpolation can give

A searching method that uses linear interpolation can give fast retrieval when the ordered data set is relatively evenly distributed over its range of possible values. With this method. the magnitude of the value x we ar ...

Q 1 identify and explain the three major interrelated tasks

Q. 1 Identify and explain the three major interrelated tasks for creating 3-D animation. a. creating the objects and scenes b. defining motion c. rendering the final animation Q. 2 Identify and explain the advantages of ...

1 implement the remaining methods of the

1. Implement the remaining methods of the TicketCounterSimulation class. 2. Modify the TicketCounterSimulation class to use seconds for the time units instead of minutes. Run an experiment with multiple simulations and p ...

1 describe all constructors of the savings account class

1. Describe all constructors of the Savings Account class. List all methods that are inherited from the Bank Account class. List all methods that are added to the Savings Account class. 2. Can you convert a superclass re ...

1 draw a network map that shows the topology of the mfn and

1. Draw a network map that shows the topology of the MFN and how the main components are connected. 2. What other information would you gather to improve your map and add more detail?

In a commentary piece on the rising cost of health

In a commentary piece on the rising cost of health insurance ("Healthy, Wealthy, and Wise," Wall Street Journal, May 4, 2004, A20), economists John Cogan, Glenn Hubbard, and Daniel Kessler state, "Each percentage-point r ...

1 in your opinion is computer forensics a viable tool in

1. In your opinion, is computer forensics a viable tool in the fight against the cyber crime epidemic? 2. Discuss the difficulties faced by cyber crime investigators. 3. Differentiate between computer and network forensi ...

A class x has 12 operations cyclomatic complexity has been

A class X has 12 operations. Cyclomatic complexity has been computed for all operationsin the OO system, and the average value of module complexity is 4. For class X, the complexityfor operations 1 to 12 is 5, 4, 3, 3, 6 ...

1 why is it important to use specific and clearly defined

1. Why is it important to use specific and clearly defined job descriptions for hiring information security professionals? 2. What functions does the CISO perform, and what are the key qualifications and requirements for ...

Consider the signalxn deltan-2deltan-1 2deltan-2-deltan-3a

Consider the signal x[n] = δ[n]-2δ[n-1]+ 2δ[n-2]-δ[n-3]. (a) Compute and plot the 4-point DFT X[k]. (b) Using the fewest number of zeros possible, zero pad x[n] so that the DFT frequency resolution is at least Ω0 = 0.1. ...

  • 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

Section onea in an atwood machine suppose two objects of

SECTION ONE (a) In an Atwood Machine, suppose two objects of unequal mass are hung vertically over a frictionless

Part 1you work in hr for a company that operates a factory

Part 1: You work in HR for a company that operates a factory manufacturing fiberglass. There are several hundred empl

Details on advanced accounting paperthis paper is intended

DETAILS ON ADVANCED ACCOUNTING PAPER This paper is intended for students to apply the theoretical knowledge around ac

Create a provider database and related reports and queries

Create a provider database and related reports and queries to capture contact information for potential PC component pro

Describe what you learned about the impact of economic

Describe what you learned about the impact of economic, social, and demographic trends affecting the US labor environmen