Ask Question, Ask an Expert

+1-415-315-9853

info@mywordsolution.com

Ask Computer Engineering Expert

problem) Show that the following two grammars are equivalent:

Grammar 1: S → abAB | ba

A → aaa

B → aA | bb

Grammar 2: S → AbAaA | abAbb | ba

A → aaa

problem) Show that the following grammar is ambiguous:

S → aSb | SS | Λ

problem) The nor of two languages is defined as follows:

A word is in nor (L1, L2) if it is in neither L1 nor L2. If L1  and L2 are regular, show that nor (L1,L2) is also regular.

problem) Minimize the following DFA:

1421_dfa.jpg

problem) Devise an NPDA to recognize the language   ambn   where m=n or m=2n

problem)

a) Show a derivation tree for the string aabbbb with the grammar:

S → AB | Λ

A → aB B → Sb

(b Describe the language generated by this grammar.

problem) using the CYK algorithm, determine whether the word aab can be generated by the following grammar:

S → AB

A → BB | a

B → AB | b

problem) A 2-track TM contains binary number (k) on track 1. Outline the operation of a TM that halts with heads over cell k on the tape. The first cell is numbered 0.

problem) Suppose we restrict a TM so that it is not allowed to prepare the symbol that it reads; in other words in the quintuple ( Qi, X,  Qj, Y, Direction) X cannot be the same symbol as Y. Does this limitation reduce the power of the TM? Give reasons for your answer.

problem) A TM tape contains a binary number with an odd number of digits. prepare a TM that Halts if the middle digit is 0 and crashes otherwise.

problem) For each of the following, circle TRUE if the statement is always correct. Otherwise, circle FALSE.

(a) TRUE   FALSE               If L1  and L2  are nonregular languages than L1  ∩ L2 must be nonregular.

(b) TRUE    FALSE            If L is a nonregular language then L must be infinite.

(c) TRUE   FALSE          If a regular expression contains a Kleene star then the language generated by the regular expression must be infinite.

(d) TRUE  FALSE            If L is a regular language then L' must be a nonregular language.

Computer Engineering, Engineering

  • Category:- Computer Engineering
  • Reference No.:- M9244

Have any Question? 


Related Questions in Computer Engineering

1 list and describe the four primary types of ups systems

1. List and describe the four primary types of UPS systems. Which is the most effective and the most expensive, and why? 2. What two critical functions are impaired when water is not available in a facility? Why are thes ...

Like any other day jim pulls into the parking lot at

Like any other day, Jim pulls into the parking lot at Pixelated Pony Corporation (PPC) for another day of work. While walking across the parking lot, he reminds himself that he needs to back up the final design of the co ...

Assignmentnbspads and consumer promotionsthis assignment

Assignment:  Ads and Consumer Promotions This assignment will assess the competency 3. Explore Ethics, Corporate Social Responsibility and Customer Communication. It seems as if many times a year a business or organizati ...

1 which fields in a log entry will be accessed for the

1. Which fields in a log entry will be accessed for the given log processing function? Assuming 64-byte cache blocks and no prefetching, how many cache misses per entry does the given function incur on average? 2. How ca ...

Using figure 2419 explain how flow control can be achieved

Using Figure 24.19, explain how flow control can be achieved at the sender site in TCP (from the sending TCP to the sending application). Draw a representation.

Discuss authorization and authentication and explain

Discuss authorization and authentication and explain forms-based-authentication. Describe the use of the ControlToValidate, Validation expression, ErrorMessage, and Enabled properties of a validation control.

Suppose you have to implement a search algorithm in a high

Suppose you have to implement a search algorithm in a high programming language such as Java or C++. You are given an array which isnotsorted and it's rather large, in the order of millions of elements. You expect that t ...

1 identify the five components of a data communications

1. Identify the five components of a data communications system. 2. What are the three criteria necessary for an effective and efficient network? 3. What are the advantages of a multipoint connection over a point-to-poin ...

A steeple-building robot looks for two blocks that are

A steeple-building robot looks for two blocks that are clear and puts one of them on top of the other (if the block being moved can be located as being on some other block or on the floor). Write down a first-order predi ...

Consider the following scenariojason from the designer

Consider the following scenario: Jason from the designer group submitted a ticket with your companies IT Help Desk stating that he could no longer access the Internet. Whenever he types a website name into his web browse ...

  • 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