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

Design a combination generation algorithm that accepts as

Design a combination generation algorithm that accepts as input a set of n characters and produces as output all combinations of size r of these characters.

You may search these questions or part of them on the web

You may search these questions or part of them on the web resource links available under "Additional Web Resources for Telecommunication & Network Security.pdf". If you do so, you must provide the reference to the resour ...

1 write a function removeat that takes three parameters an

1. Write a function, removeAt, that takes three parameters: an array of integers, the number of elements in the array, and an integer (say, index). The function should delete the array element indicated by index. If inde ...

Design values and adjustment factors in the following

Design values and adjustment factors in the following problems are to be taken from the 1997 NDS. Assume wood will be used in dry-service conditions and at normal temperatures unless otherwise noted. a. Describe softwood ...

What is the phase shift for the followinga a sine wave with

What is the phase shift for the following? a. A sine wave with the maximum amplitude at time zero b. A sine wave with maximum amplitude after 1/4 cycle c. A sine wave with zero amplitude after 3/4 cycle and increasing

Although most systems allow objects to have only one owner

Although most systems allow objects to have only one owner, it is possible for an object to have two (or more) owners. Consider ownership as a right that allows the changing of capabilities (or access control lists). How ...

In tcp assume a client has 100 bytes to send the client

In TCP, assume a client has 100 bytes to send. The client creates 10 bytes at a time in each 10 ms and delivers them to the transport layer. The server acknowledges each segment immediately or if a timer times out at 50 ...

A robot must find the shortest path between a starting

A robot must find the shortest path between a starting point. s. and a goal location. g. in the two-dimensional space populated by polygonal obstacles shown here. Assume the robot is of infinitesimal size. The path can b ...

1 an opaque urn contains three diamonds four rubies and two

1. An opaque urn contains three diamonds, four rubies, and two pearls. Construct a flowchart that describes the following events: Take a gem from the urn. If it is a diamond, lay it aside. If it is not a diamond, return ...

1 assume a private internet uses a protocol suite totally

1. Assume a private internet uses a protocol suite totally different from the TCP/ IP protocol suite. Can this internet still use the services of UDP or TCP as an end-to-end vehicle of message communication? 2. Can you e ...

  • 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

WalMart Identification of theory and critical discussion

Drawing on the prescribed text and/or relevant academic literature, produce a paper which discusses the nature of group

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