Ask Question, Ask an Expert

+61-413 786 465

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

Assume that the hypothetical economy of mo has 8 workers in

Assume that the hypothetical economy of Mo has 8 workers in year 1, each working 1,500 hours per year (50 weeks at 30 hours per week). The total input of labor is 12,000 hours. Productivity (average real output per hour ...

Question part 1 capstone exam - submit to the unit 2 ip

Question: Part 1: Capstone Exam - Submit to the Unit 2 IP Area This exam assignment may only be completed through the end of Unit 4. It will not be accepted late during Unit 5. This exam may only be completed on a comput ...

Given an undirected graph with both positive and negative

Given an undirected graph with both positive and negative edge weights, design an algorithm to find a maximum spanning forest with the largest total edge weights.

Please discuss the data hazards associated with pipelining

Please discuss the data hazards associated with pipelining with an example and how these hazards impact the performance gain associated with pipelining.

A manager has a 250 million portfolio that consists of 40

A manager has a $250 million portfolio that consists of 40% stock and 60% bonds. The beta of the stock position is 1.4. The modified duration of the bond position is 5. The manager wishes to achieve an effective mix of 7 ...

Give examples of how dominos has adapted its global

Give examples of how Domino's has adapted its global marketing mix to meet the needs of local consumers. Are you their customer? If so, why?

Question whats the roles of user roles and why are they

Question : What's the roles of user roles and why are they necessary for Linux? How are these roles and permission similar and different from other types of users and other operating systems?

Right now the following information is in the header file c

RIght now, the following information is in the header file (C language). # ifndef ArrayBagStack # define ArrayBagStack # define TYPE int # define EQ(a, b) (a == b) struct arrayBagStack { TYPE data [100]; int count; }; Qu ...

Question suppose that a bayesian spam filter is trained on

Question : Suppose that a Bayesian spam filter is trained on a set of 10000 spam messages and 5000 messages that are not spam. The word "opportunity" appears in 175 spam messages and 20 messages that are not spam. Would ...

A chemistry student needsnbsp150 ml of acetone for an

A chemistry student needs 15.0 mL of acetone for an experiment. By consulting the  CRC Handbook of Chemistry and Physics , the student discovers that the density of acetone is 0.790 g.cm^-3. Calculate the mass of acetone ...

  • 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

Why might a bank avoid the use of interest rate swaps even

Why might a bank avoid the use of interest rate swaps, even when the institution is exposed to significant interest rate

Describe the difference between zero coupon bonds and

Describe the difference between zero coupon bonds and coupon bonds. Under what conditions will a coupon bond sell at a p

Compute the present value of an annuity of 880 per year

Compute the present value of an annuity of $ 880 per year for 16 years, given a discount rate of 6 percent per annum. As

Compute the present value of an 1150 payment made in ten

Compute the present value of an $1,150 payment made in ten years when the discount rate is 12 percent. (Do not round int

Compute the present value of an annuity of 699 per year

Compute the present value of an annuity of $ 699 per year for 19 years, given a discount rate of 6 percent per annum. As