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

Garber and skinner suggest that the large per capital

Garber and Skinner suggest that the large per capital health spending in the US (and relatively low returns to health) are due to productive and allocative inefficiencies. Which inefficiency (if either) do you think char ...

Suppose that one person in 750 people has a rare genetic

Suppose that one person in 750 people has a rare genetic disease. There is an excellent test for the disease; 99% of people with the disease test positive and only 0.01% who do not have the disease test positive. (a) Wha ...

Requirementsnew payroll functionality to allow global

Requirements New payroll functionality to allow global employee to submit banking information to get paid electronically (i.e. direct deposit paycheck to bank account). Initial pilot has 3 countries in Asia Pacific, Euro ...

What is the broadcast domain and ports for hubs and

What is the Broadcast Domain and Ports for hubs and bridges?

Which of the subsequent statements is correct with regard

Which of the subsequent statements is correct with regard to distributed systems ? a. Distributed system represents a world read of the network and considers it as a virtual uniprocessor system by dominant and managing r ...

You are starting a company on a tight budget you can get

You are starting a company on a tight budget. You can get DSL line to your office with a static IP address, but ISP does not offer any DNS services. At this point you do not want to set up your own DNS, so you want to fi ...

Single purpose processorsdesign the sequence recognizer for

Single Purpose Processors Design the sequence recognizer for 101 . Perform the following steps: - the state diagram -the state table -K-map -Simplification of the function by using the K-map -Circuit (logic diagram).

Question show step by step how bubble sort will work on the

Question : Show step by step how bubble sort will work on the following array: 10, 4, 9, 7, 3. Draw the array for every candidate swapping in every iteration separately. Mark the swapped elements and mark the iterations ...

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 ...

A 2-year treasury security currently earns 197 percent over

A 2-year Treasury security currently earns 1.97 percent. Over the next two years, the real risk-free rate is expected to be 1.00 percent per year and the inflation premium is expected to be 0.60 percent per year. Calcula ...

  • 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