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

A calling agency has data showing that the average response

A calling agency has data showing that the average response time is 5.6 minutes with a standard deviation of 1.8. The manager wants to know how much time is required for 75% of all calls to be handled (in other words, th ...

Question suppose 4 packets of a message each of l bits

Question : Suppose 4 packets of a message, each of L bits arrive at a switch (router) and traverse a link with rate R bps to the destination. Further, suppose that the link is free when the first packet arrives, and the ...

Question suppose message a is one block long suppose that

Question : Suppose message (a) is one block long. Suppose that an attacker has received the MAC (t) for a using CBC-MAC under some random key unknown to the attacker. Explain how to forge the MAC for a two-block message ...

Question the use of encryption can have adverse effects on

Question: The use of encryption can have adverse effects on incident response and incident investigations; however, from a security standpoint, encryption is a major component in network confidentiality. Present your arg ...

You are given a test to enter graduate school you must

You are given a test to enter graduate school. You must select 10 of the 13 essay questions to answer to determine your writing skills. How many ways can you select those questions?

Question suppose that your uncle is a real estate agent and

Question : Suppose that your uncle is a real estate agent and he decided to have a web-site to list his available real estate properties. And use a laptop computer to show clients these properties. What hardware is neede ...

In c languageread a double number as 2 digits after the

In C language: Read a double number as 2 digits after the decimal point. The number should have at least 6 digits BEFORE the decimal point. Extract all digits at even positions. Print them in reverse order. Extract all d ...

Question suppose you want to perform two sums one is a sum

Question : Suppose you want to perform two sums: one is a sum of 10 scalar variables, and one is a matrix sum of a pair of two-dimensional arrays, with dimensions 10 by 10. What speed-up do you get with 10 versus 100 pro ...

A chest has 3 drawers d1 has two silver coins s d2 has one

A chest has 3 drawers: (D 1 ) has two silver coins (S), (D 2 ) has one silver (S) and one gold (G), and (D 3 ) has two gold (G) coins. The drawer and coin were both randomly selected. Use the law of total probability to ...

A a simple encryption of a character a can be performed by

a) A simple encryption of a character A can be performed by exclusive-ORing A with some key K to produce the encrypted value E. The original value A can be recovered by exclusive-ORing again with the same key. Write a c/ ...

  • 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