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

Is the process before and after the swap are the same give

Is the Process before and after the swap are the same? Give reason.

Look up the w3c standard on xmlhttprequest what arguments

Look up the W3C standard on XMLHttpRequest. What arguments can the send method of this interface support? What is the purpose of the XMLHttpRequest responseType property, and what values can you assign to this property? ...

Cloud computing and big data ecosystems design-trending

Cloud Computing and Big Data Ecosystems Design- Trending Topics in Twitter Description: The goal of this assignment is to implement a Java application that reads tweets from both the Twitter Streaming API and preloaded l ...

How would goal setting theory or equity theory be related

How would goal setting theory or equity theory be related to a customers motivation to choose a specific title. In this case the customer is a netflix customer. I understand the concept of each theory but am having troub ...

Semi-supervised classification active learning and transfer

Semi-supervised classification, active learning, and transfer learning are useful for situations in which unlabeled data are abundant. (a) Describe semi-supervised classification, active learning, and transfer learning. ...

Powerenergy quantification a server farm has most of its

Power/Energy quantification. A server farm has most of its servers operating at only 50% capacity. The problem is that the power draw from these servers does not scale linearly with the reduced load; that is, when the se ...

A brief description of three instances in which

A brief description of three instances in which communication technology tools other than social media might be used for a public health campaign and explain why. Explain one challenge to using communication technology t ...

When creating the logic for a new program which is the best

When creating the logic for a new program, which is the best way to go about it, pseudo code or flowcharts?

Assignment exploring the machinein this assignment you will

Assignment: Exploring the Machine In this assignment, you will explore a computer (i.e., a Windows PC or a Mac computer). Specifically, you will view the system's general information, create a folder on the desktop of th ...

What in general is the relationship between the present

What, in general, is the relationship between the present value of a discount bond and its time to maturity?

  • 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

A cola-dispensing machine is set to dispense 9 ounces of

A cola-dispensing machine is set to dispense 9 ounces of cola per cup, with a standard deviation of 1.0 ounce. The manuf

What is marketingbullwhat is marketing think back to your

What is Marketing? • "What is marketing"? Think back to your impressions before you started this class versus how you

Question -your client david smith runs a small it

QUESTION - Your client, David Smith runs a small IT consulting business specialising in computer software and techno

Inspection of a random sample of 22 aircraft showed that 15

Inspection of a random sample of 22 aircraft showed that 15 needed repairs to fix a wiring problem that might compromise

Effective hrmquestionhow can an effective hrm system help

Effective HRM Question How can an effective HRM system help facilitate the achievement of an organization's strate