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

Discussion criminal background checksread the article

Discussion: Criminal Background Checks Read the article titled "Why Aren't Business Ethics Classes Making Businesses More Ethical?" located at The Wall S ...

Assessment activity instructionsdemonstrate your

Assessment Activity Instructions Demonstrate your understanding and knowledge gained about session's material. Complete with a short discussion (one paragraph) for each question on a Word document and upload through the  ...

1 compare the authorization model used by the network

1. Compare the authorization model used by the network operating systems (NOS) to that used by the old stand-alone operating systems. 2. List and discuss the most common access privileges in a computing system. 3. Discus ...

Assignmenttopic the effect of virtual achievements on

Assignment Topic :The Effect of Virtual Achievements on Student Engagement For this task, I need help in developing a narrative about my topic (above), and an outline of the collegiate dissertation process, to submit for ...

1 an ipv6 packet consists of a base header and a tcp

1. An IPv6 packet consists of a base header and a TCP segment. The length of data is 128,000 bytes (jumbo payload). Show the packet and enter a value for each field. 2. Which ICMP messages contain part of the IP datagram ...

Examproblem i-part a your systems analysis team is close to

Exam Problem I- Part A: Your systems analysis team is close to completing a system for Meecham Feeds. Roger is quite confident that the programs that he has written for Meecham's inventory system will perform as necessar ...

Use the probability density function of problem 414aa

Use the probability density function of Problem 4.14a. a. Design the four-level optimum-uniform quantizer. Calculate the mean square error and the entropy of the output. b. Design the four-level Lloyd-Max quantizer (or t ...

1 discuss two lan technologies that are not ethernet or

1. Discuss two LAN technologies that are NOT Ethernet or token ring. 2. Why is Ethernet technology more appealing to users than the rest of the LAN technologies? 3. What do you think are the weak points of TCP/IP? 4. Dis ...

Implement the bankers algorithm- needed before the end of

Implement the Banker's algorithm- needed before the end of today Implement the Banker's algorithm for deadlock avoidance, that works on a given set of N processes and M resource types (N The input data and result is then ...

In 300 words or more plesae answer the followinginformation

In 300 words or more plesae answer the following: Information technology professionals face many ethical obligations, conflicts, and dilemmas. Discuss ethical issues an IT professional might face. Consider the new trends ...

  • 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