Ask Question, Ask an Expert


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:


problem) Devise an NPDA to recognize the language   ambn   where m=n or m=2n


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

Problem 3- network design for schoolnetwork design for

Problem 3- Network Design for School: Network Design for Schoola network has to be designed for a school. There are100 computers in the school. And has 5 Labs each of them consisted of 31 computersThe users in the lab sh ...

Overview of business casealive amp boating aampb is a small

Overview of business case: Alive & Boating (A&B) is a small start-up company that sells small boats in Wagga. A&B keeps its models in several showrooms across the city. At this stage customers cannot view the available m ...

How do screened host architectures for firewalls differ

How do screened host architectures for firewalls differ from screened subnet firewall architectures? Which of these offers more security for the information assets that remain on the trusted network? What a sacrificial h ...

Implement the fibonacci algorithm as a function that

Implement the Fibonacci algorithm as a function that accepts as input two consecutive Fibonacci numbers and returns as output the next Fibonacci number.

1 a grab bag adt is similar to the bag adt with one

1. A Grab Bag ADT is similar to the Bag ADT with one difference. A grab bag does not have a remove() operation, but in place of it has a grabItem() operation, which allows for the random removal of an item from the bag. ...

Design a security service that provides data integrity data

Design a security service that provides data integrity, data confidentiality and nonrepudiation using public-key cryptography in a two-party communication system over an insecure channel. Give a rationale that data integ ...

Questionconsider the following case of decision-making on

Question. Consider the following case of decision-making on loan applications.  You are a bank executive with thousands of records on customers who were given loans.  Each record has many fields, such as amount of loan, ...

1 what is machine learning2 what is the relationship

1) What is machine learning? 2) What is the relationship between Machine Learning & Big Data? 3) Provide a few business cases where Machine Learning would help. (Extra credit) What are the different types of Machine Lear ...

Implement the following algorithm to construct magic

Implement the following algorithm to construct magic n-by-n 2 squares; it works only if n is odd. Place a 1 in the middle of the bottom row. After k has been placed in the (i, j) square, place k + 1 into the square to th ...

Calculate the total number of bits required for the cache

Calculate the total number of bits required for the cache listed above, assuming a 32-bit address. Given that total size, find the total size of the closest direct-mapped cache with 16-word blocks of equal size or greate ...

  • 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