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 write a program to plot the string hello using only lines

1. Write a program to plot the string "HELLO", using only lines and circles. Do not call drawString, and do not use System.out. Make classes LetterH, LetterE, LetterL, and LetterO. 2. Write a program that displays the Ol ...

1 prove that two users who perform a diffie-hellman key

1. Prove that two users who perform a Diffie-Hellman key exchange will have the same shared key. 2. In the example enciphering HELLO WORLD using the RSA cipher (the second example in Section 9.3.2), the modulus was chose ...

1 what is the standard for encryption currently recommended

1. What is the standard for encryption currently recommended by NIST? 2. What is the most popular symmetric encryption system used over the Web? The most popular asymmetric system? Hybrid system?

1 what is a vulnerability scanner how is it used to improve

1. What is a vulnerability scanner? How is it used to improve security? 2. What is the difference between active and passive vulnerability scanners? 3. What kind of data and information can be found using a packet sniffe ...

1 what is the difference between an actionevent and a

1. What is the difference between an ActionEvent and a MouseEvent? 2. Why does the ActionListener interface have only one method, whereas the MouseListener has five methods? 3. Can a class be an event source for multiple ...

In this problem we want to study the clock frequency

In this problem we want to study the clock frequency requirements for a hardware implementation of DES in real-world applications. The speed of a DES implementation is mainly determined by the time required to do one cor ...

1 do some research regarding tcp window scaling find out if

1. Do some research regarding TCP window scaling. Find out if the OS on your computer uses it by default and, if not, if there's a mechanism for configuring the OS to use it. 2. Do some research on distributed computing. ...

1 suppose the stock of capital and the workforce are both

1. Suppose the stock of capital and the workforce are both increasing at 3 percent annually in the country of Wholand. At the same time, real output is growing at 6 percent. How is that possible in the short run and in t ...

1 can you find an analogy in our daily life as to when we

1. Can you find an analogy in our daily life as to when we use two separate connections in communication similar to the control and data connections in FTP? 2. FTP uses two separate well-known port numbers for control an ...

1 the development of a forensic lab for computers and

1. The development of a forensic lab for computers and mobile devices involves numerous specialized tools. Describe both hardware and software tools that might be utilized in such a lab. 2. Select ONE type of software to ...

  • 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