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

Think about a specific healthcare organization are there

Think about a specific healthcare organization: Are there any differences for creating an effective delivery system? Who are the important stakeholders in a healthcare delivery system? This Journal has no entries.

1 the discussion of acyclic creates imposes constraints on

1. The discussion of acyclic creates imposes constraints on the types of created subjects but not on the types of created objects. Why not? 2. Prove that if a graph for cc is constructed and has no loops, the system is a ...

1 assuming that the l1 hit time determines the cycle times

1. Assuming that the L1 hit time determines the cycle times for P1 and P2, what are their respective clock rates? 2. What is the Average Memory Access Time for P1 and P2? 3. Assuming a base CPI of 1.0 without any memory ...

Design an algorithm for computing vn for any positive

Design an algorithm for computing vn for any positive integer n. Besides assignment and comparison, your algorithm may only use the four basic arithmetical operations.

When people describe client-server architecture they are

When people describe client-server architecture, they are usually referring to a system in which a large server is serving a client on a PC. With X Window, the reverse is frequently the case. Explain.

Question 1 an example of the neuron model is the sigmoid

Question 1. An example of the neuron model is the sigmoid function which is defined by: φ(v)=1/(1+exp?(-v)) For this problem, you need to prove that (∂φ(v))/∂v=φ(v)(1-φ(v)) Question 2. Consider the following cost functio ...

1 what are the primary objectives of the internal

1. What are the primary objectives of the internal monitoring domain? 2. What is the objective of the planning and risk assessment domain of the maintenance model? Why is this important?

1 in what fraction of all cycles is the data memory used2

1. In what fraction of all cycles is the data memory used? 2. In what fraction of all cycles is the input of the sign-extend circuit needed? What is this circuit doing in cycles in which its input is not needed? 3. When ...

1 when looking at the chronology of the development of the

1) When looking at the chronology of the development of the Internet, which development do you believe to be the most important? Why? 2) In terms of online users, are the genders equally represented? How about for minori ...

Suppose a chosen-ciphertext attacker cannot recover the

Suppose a chosen-ciphertext attacker cannot recover the secret decryption key loran encryption scheme. Does this mean the encryption scheme is secure? Consider a symmetric-key cryptosystem in which cryptographic keys are ...

  • 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