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 using the implementation of the ipaddresses class

1. Using the implementation of the IPAddresses class developed in this chapter, write a method that displays the IP addresses stored in the class in ascending order. Use the method in a program. 2. Write a program that s ...

Write your own bitarray class without inheriting from the

Write your own BitArray class (without inheriting from the BitArray class) that includes a conversion method that takes Boolean values and converts them to bit values. Hint: use a BitArray as the main data structure of t ...

Based on the design requirements and decisions that have

Based on the design requirements and decisions that have been made, what wireless access points would you recommend for WVCC? Do some Internet research to find an access point that will meet WVCC's needs and write two or ...

Apa fortmat - 300 words-nbspreferences pleasethe family

APA fortmat - 300 words-  references please. The Family Education Rights and Privacy Act (FERPA) was passed in 1974 to protect the privacy rights of students in higher education institutions. It is appropriate to mention ...

As we have seen in this chapter public-key cryptography can

As we have seen in this chapter, public-key cryptography can be used for encryption and key exchange. Furthermore, it has some properties (such as nonrepudiation) which are not offered by secret key cryptography. So why ...

1 discuss a good security auditing system2 compare or

1. Discuss a good security auditing system. 2. Compare or discuss the differences between any two security systems. 3. Discuss human error or human factors as a major security threat. 4. What is the best way to deal with ...

1 open the netlogo flocking model from the biology section

1. Open the NetLogo Flocking model from the Biology section of the models library, which shows emergent rules for generating bird flocks. Can you add a predator bird that changes the other birds ' behavior? 2. Choose any ...

One of the objects groups that can be managed is the ip

One of the objects (groups) that can be managed is the ip group with the object identifier ( in which ( is the identifier of MIB-2 and (4) defines the ip group. In an agent, this object has 20 s ...

Read the case study titled a patient information system for

Read the case study titled "A Patient Information System for Mental Health Care", located in Chapter 1 of your textbook. Develop an overall architecture for the system described in the assigned reading. Your architecture ...

1 analyze the quick sort algorithm to show the worst case

1. Analyze the quick sort algorithm to show the worst case time is O(n 2 ). 2. Analyze the mergeVirtualSeq() function and show that it is a linear time operation in the worst case. 3. Analyze the linked list version of t ...

  • 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