Ask Question, Ask an Expert


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:


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


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

For many years industries and financial institutions hired

For many years, industries and financial institutions hired people who broke into their systems once those people were released from prison. Now, such a conviction tends to prevent such people from being hired. Why you t ...

1 what is physical security what are the primary threats to

1. What is physical security? What are the primary threats to physical security? How are they made manifest in attacks against the organization? 2. What are the roles of IT, security, and general management with regard t ...

Assignmentyou are working for a retirement planners company

Assignment You are working for a Retirement Planners company that helps customers plan retirement parties. The company has to track all retirement parties for which it is providing planning services. However, since you a ...

Implement a class roachpopulation that simulates the growth

Implement a class RoachPopulation that simulates the growth of a roach population. The constructor takes the size of the initial roach population. The breed method simulates a period in which the roaches breed, which dou ...

1 describe all constructors of the savings account class

1. Describe all constructors of the Savings Account class. List all methods that are inherited from the Bank Account class. List all methods that are added to the Savings Account class. 2. Can you convert a superclass re ...

1 determine the least upper bound and greatest lower bound

1. Determine the least upper bound and greatest lower bound for the pair of complex integers a and b in the subset C´ used in the examples. 2. Prove that the set of all subsets of a given set S (called the power set of S ...

1 assume there is a server with the domain name

1. Assume there is a server with the domain name a. Show an HTTP request that needs to retrieve the document /usr/users/doc. The client accepts MIME version 1, GIF or JPEG images, but the document should ...

The problem of the dutch national flag involves starting

The problem of the Dutch national flag involves starting out with a row of n buckets, i.e. bucket [1..n], each bucket containing a single pebble that is either red, white or blue. The task is to arrange the pebbles so th ...

1 who should pay for the expenses of certification why2

1. Who should pay for the expenses of certification? Why? 2. List and describe the standard personnel practices that are part of the information security function. What happens to these practices when they are integrated ...

Write a method randomshape that randomly generates objects

Write a method randomShape that randomly generates objects implementing the Shape interface: some mixture of rectangles, ellipses, and lines, with random positions. Call it 10 times and draw all of them.

  • 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