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

1 http version 11 defines the persistent connection as the

1. HTTP version 1.1 defines the persistent connection as the default connection. Using RFC 2616, find out how a client or server can change this default situation\ to nonpersistent. 2. In SMTP, a sender sends unformatted ...

Design a help-desk priority manager store help requests

Design a help-desk priority manager. Store help requests stored in a text file with the following structure: priority, id of requesting party, time of request The priority is an integer in the range 1-5 with 1 being the ...

A robot must find the shortest path between a starting

A robot must find the shortest path between a starting point. s. and a goal location. g. in the two-dimensional space populated by polygonal obstacles shown here. Assume the robot is of infinitesimal size. The path can b ...

Assume we are searching a tree with branching factor b

Assume we are searching a tree with branching factor b. However, we do not know that we are really searching a tree, so we are considering checking each state description generated to see if it matches a previously gener ...

1 add a function to the binarysearchtree class that counts

1. Add a function to the BinarySearchTree class that counts the number of edges in a tree. 2. Rewrite Exercise 1 so that it stores the words from a text file. Display all the words in the file and the number of times the ...

Examproblem i-part a your systems analysis team is close to

Exam Problem I- Part A: Your systems analysis team is close to completing a system for Meecham Feeds. Roger is quite confident that the programs that he has written for Meecham's inventory system will perform as necessar ...

1 what is radius what advantage does it have over tacacs2

1. What is RADIUS? What advantage does it have over TACACS? 2. What is a content filter? Where is it placed in the network to gain the best result for the organization? 3. What is a VPN? Why is it becoming more widely us ...

1 explain the advantages of ipv6 when compared to ipv42

1. Explain the advantages of IPv6 when compared to IPv4. 2. Explain the use of the flow field in IPv6. What is the potential application of this field? 3. Distinguish between compatible and mapped addresses and explain t ...

Q1 analysis of algorithms for each expression in the len

Q1. Analysis of algorithms: For each expression in the leN column, give the best matching description from the right column. ______N 3 ______1 + 2 + 3 + 4 + 5 + : : : + N                                         A. 1/2N 2 ...

Write a c function minimum this function is passed a

Write a C++ function minimum. This function is passed a vector parameter and returns the smallest value stored in the array list. Write an additional code fragment to test this function. Include any declarations and init ...

  • 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