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

1 calculate the mtbf for each of the devices in the table2

1. Calculate the MTBF for each of the devices in the table. 2. Calculate the availability for each of the devices in the table. 3. What happens to availability as the MTTR approaches 0? Is this a realistic situation? 4. ...

1 in sctp a packet is carrying a cookie echo message and a

1. In SCTP, a packet is carrying a COOKIE ECHO message and a DATA chunk. If the size of the cookie is 200 bytes and that of the user data is 20 bytes, what is the size of the packet? 2. In SCTP, a packet is carrying a CO ...

When does an ospf router send each of the following

When does an OSPF router send each of the following messages? a. hello b. data description c. link-state request d. link-state update e. link-state acknowledgment

1 write a program that can read an indefinite number of

1. Write a program that can read an indefinite number of lines of VB.NET code and store reserved words in one linked list and identifiers and literals in another linked list. When the program has finished reading input, ...

The baypoint group tbg needs your help with a presentation

The Baypoint Group (TBG) needs your help with a presentation for Academic Computing Services (ACS), a nationwide organization that assists colleges and universities with technology issues. ACS needs more information abou ...

1 list three types of autonomous systems ass described in

1. List three types of autonomous systems (ASs) described in the text, and make a comparison between them. 2. Explain the concept of hop count in RIP. Can you explain why no hop is counted between N1 and R1 in Figure 20. ...

From the weekly readings and e-activity analyze the key

From the weekly readings and e-Activity, analyze the key influences that the theoretical and practical aspects of public leadership may exert upon a public leader's performance. Provide two (2) examples of these influenc ...

1 prove or disprove that state-based logging and

1. Prove or disprove that state-based logging and transition-based logging are equivalent if and only if the state of the system at the first transition is recorded. 2. Suppose a remote host begins the TCP three-way hand ...

1 discuss the role of certificate authentication in

1. Discuss the role of certificate authentication in e-commerce. 2. Many predict that the future of e-commerce is pegged on the successful implementation of authentication. Discuss. 3. Discuss the role of public-key auth ...

Design an algorithm that generates all permutations of the

Design an algorithm that generates all permutations of the first n integers taken r at a time and allowing unrestricted repetitions. This is sometimes referred to as sample generation. The values of n and r must be great ...

  • 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

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

Describe what you learned about the impact of economic

Describe what you learned about the impact of economic, social, and demographic trends affecting the US labor environmen