Ask Question, Ask an Expert


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.


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

1 the maximum window size of the tcp was originally

1. The maximum window size of the TCP was originally designed to be 64 KB (which means 64 × 1024 = 65,536 or actually 65,535). Can you think of a reason for this? 2. What is the maximum size of the TCP header? What is th ...

Soon after the board of directors meeting charlie was

Soon after the board of directors meeting, Charlie was promoted to Chief Information Security Officer, a new position that reports to the CIO, Gladys Williams, and that was created to provide leadership for SLS's efforts ...

1 a network consists of n hosts assuming that cryptographic

1. A network consists of n hosts. Assuming that cryptographic keys are distributed on a per-hostpair basis, compute how many different keys are required. 2. One cryptographic checksum is computed by applying the DES in C ...

1 find at least two new coin denominations that make the

1. Find at least two new coin denominations that make the greedy algorithm for coin changing shown in the chapter produce suboptimal results. 2. Using a "commercial" compression program, such as WinZip, compress a small ...

Consider the following problem descriptionemployees receive

Consider the following problem description: Employees receive their biweekly paychecks. They are paid their hourly rates for each hour worked; however, if they worked more than 40 hours per week, they are paid at 150 per ...

Visit the nist web site and view the document announcing

Visit the NIST Web site and view the document "Announcing the Advanced Encryption Standard (AES)" which can be found at fips197/fips-197.pdf. Review the FIPS-197 standard. Examine ...

1 search the web for the forum of incident response and

1. Search the Web for the Forum of Incident Response and Security Teams (FIRST). In your own words, what is the forum's mission? 2. Search the Web for two or more sites that discuss the ongoing responsibilities of the se ...

Ups system integration challengesafter you have read the

UPS system integration challenges After you have read the case study, answer the following questions: 1. What are some of the system integration challenges faced by UPS? 2. Discuss the systems integration solutions at UP ...

1 what is the difference between the paintcomponent and

1. What is the difference between the paintComponent and repaint methods? 2. What is the difference between a frame and a panel? 3. Have the Die class of Chapter 6 implement the Measurable interface. Generate dice, cast ...

1 the stream function for an incompressible two-dimensional

1. The stream function for an incompressible, two-dimensional flow field is For this flow field, plot several streamlines for 2. For the case of a source at the origin with a uniform free stream plot the streamline ψ = 0 ...

  • 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