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

How many independent variables can be depicted in a scatter

How many independent variables can be depicted in a scatter plot? What are some of the difficulties in visualizing data in a scatter plot? Are these difficulties true for all types of scatter plots? Suggest alternatives ...

Self-evaluation of your paperthe following topics will

Self-Evaluation of Your Paper The following topic(s) will demonstrate what the discussion is about, but feel free to branch off or expand on the topics. At the end of the discussion, you will be asked to craft a 150 word ...

What are the typical challenges on software projects

What are the typical challenges on software projects related to managing the customer? What are the typical challenges on software projects related to managing suppliers?

M repeat part a only of problem a33 for a machine that is

[M] Repeat part (a) only of Problem A.33 for a machine that is to recognize the occurrence of either of the subsequences 011 and 010 in the input sequence, including the cases where overlap occurs. For example, the input ...

How does a weighted dimension score differ from a raw

How does a weighted dimension score differ from a raw dimension score?

Q1 prove or disprove each of the following relational

Q1. Prove or disprove each of the following relational algebra identities. These means that if they are true of all relations R and S of the same arity, then give a formal proof, otherwise provide a counterexample of two ...

Consider the following tablea write sql statements to

Consider the following table: A. Write SQL statements to display the values of any rows that violate these functional dependencies B. If no data violate these functional dependencies, can we assume that they are valid? W ...

Scenario your system was running fine but you occasionally

Scenario: Your system was running fine, but you occasionally notice the sound output was "glitchy" and you decide to add a sound card. As luck would have it, a friend gave you his old sound card from a system he threw aw ...

It should be clear that disk striping can improve the data

It should be clear that disk striping can improve the data transfer rate when the strip size is small compared to the I/O request size. It should also be clear that RAID 0 provides improved performance relative to a sing ...

What is the advantages and disadvantages of the world bank

What is the advantages and disadvantages of the world bank and the international monetary fund?

  • 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

A cola-dispensing machine is set to dispense 9 ounces of

A cola-dispensing machine is set to dispense 9 ounces of cola per cup, with a standard deviation of 1.0 ounce. The manuf

What is marketingbullwhat is marketing think back to your

What is Marketing? • "What is marketing"? Think back to your impressions before you started this class versus how you

Question -your client david smith runs a small it

QUESTION - Your client, David Smith runs a small IT consulting business specialising in computer software and techno

Inspection of a random sample of 22 aircraft showed that 15

Inspection of a random sample of 22 aircraft showed that 15 needed repairs to fix a wiring problem that might compromise

Effective hrmquestionhow can an effective hrm system help

Effective HRM Question How can an effective HRM system help facilitate the achievement of an organization's strate