Ask Question, Ask an Expert


Ask Computer Engineering Expert

Q1. Let  ∑ = {0,1}. Define the following language:

L = {x | x contains an equal number of occurrences of 01 and 10}

Either prove L is regular (by constructing a DFA/NFA or a regex) or prove that it is not regular using the Pumping Lemma for regular languages.

Q2. Given languages L, L' (over ∑ ), define the shuffle of L, L' to be

Shuffle(L, L') = {x1y1x2y2......xnyn | xi ∈ L and yi ∈ L' for i = 1,......, n}
Suppose that M = ( ∑, Q, q0,δ, F) is a DFA for L and M0 = (∑ ,Q', q0',δ', F') is a DFA for L'. Construct an NFA that accepts Shuffle(L).
[This proves that Shu e is a closed regular operator, i.e., this proves that if L; L0 are regular, then Shu e(L; L0) is also regular.]

Q3. Let   ∑={a, b, c}. Prove that the following language (defined over)

L = {uvuvu | u ∈ {a, b}* ; v ∈ {b; c}*} is not regular.
[HINT: Clean up and then use the pumping lemma for regular languages.]

Q4. Prove that the following languages are context-free by constructing the a context-free grammar for L1 and a push-down automata for L2.

(a) L1 = {ambmcn | m  ≥ 0,  n ≥ 0}

(b) L2 = {ambncn |m  ≥ 0,  n  ≥ 0}


(c) What is L1 ∩ L2? [Use set notation.]

(d) TRUE or FALSE: The intersection of any two context-free languages gives a context- free language.

Q5. Prove that

L = {ambn |m ≠ n and 2m ≠ n}

is a context-free language.

Q6. Suppose L is a context-free language and L' is regular. Show that L ∩ L' is a context- free language. Specifically, if you're given a PDA diagram of L and a DFA diagram for L',describe informally how to draw a PDA diagram for L ∩ L'.

[... it's even better if you can describe the construction of L∩L' formally but you don't have
Q7. (a) A Turing machine M is considered a DFA1 if the read/prepare head always moves to the right and it halts (i.e., enters its qaccept or qreject) when it reads a space (or blank) character on the input tape. Note that a DFA1 is like a DFA except that it must have exactly 1 accept state. (A DFA can have any number of accept states.) Is the following language:

AcceptDFA1 = {#| M is a DFA1 and accepts w}

a Turing{decidable language? If it is, describe clearly how to construct a Turing decider (i.e.,a Turing machine that always halts) that accepts the language. Otherwise prove that it's not decidable.

(b) Consider the following language:

NonEmptyTM = {#| M is a Turing machine and L(M) ≠0}

Is NonEmptyTM a Turing-decidable language?

[This is the only TM problem but it actually requires very little TM knowledge. You have everything you need to solve this problem if have a general understanding of TMs and you have paid attention to the Wednesday and Friday classes during the last week.]

Q8. This is the problem for the second version of the final exam. You only need to attempt one of the three parts. Do not turn in any work for Q1-Q7 if you plan to turn in work for Q8, or you will get an immediate 0.

1. Given two words x,y ∈ ∑*  , a DFA M separates x, y if L accepts either x or y but not both. What is the smallest number of states you need to construct a DFA that can separate any pair of distinct words of length ≤ n?

2. Consider the following problem: Given a PDA M and an integer n, is it true that ∑n ⊆ L(M)? The corresponding language is L = {#| M is a PDA and ∑n ⊆ L(M)} Is L regular, context-free, Turing{decidable, Turing{recognizable, not Turing{recognizable?

3. Either prove P = NP or P ≠ NP.

Computer Engineering, Engineering

  • Category:- Computer Engineering
  • Reference No.:- M92027

Have any Question? 

Related Questions in Computer Engineering

1 when is the ir plan used2 when is the dr plan used3 when

1. When is the IR plan used? 2. When is the DR plan used? 3. When is the BC plan used? How do you determine when to use the IR, DR, and BC plans?

A year with 366 days is called a leap year a year is a leap

A year with 366 days is called a leap year. A year is a leap year if it is divisible by 4 (for example, 1980). However, since the introduction of the Gregorian calendar on October 15, 1582, a year is not a leap year if i ...

1 describe all constructors of the savings account class

1. Describe all constructors of the Savings Account class. List all methods that are inherited from the Bank Account class. List all methods that are added to the Savings Account class. 2. Can you convert a superclass re ...

1 we would like to execute the loop below as efficiently as

1. We would like to execute the loop below as efficiently as possible. We have two different machines, a MIMD machine and a SIMD machine. 2. For a 4 CPU MIMD machine, show the sequence of MIPS instructions that you would ...

In a company all files which are sent on the network are

In a company, all files which are sent on the network are automatically encrypted by using AES-128 in CBC mode. A fixed key is used, and the IV is changed once per day. The network encryption is file-based, so that the I ...

Make a class employee with a name and salary make a class

Make a class Employee with a name and salary. Make a class Manager inherit from Employee. Add an instance variable, named department, of type String. Supply a method to String that prints the manager's name, department, ...

Write a function that accepts as arguments the following a

Write a function that accepts as arguments the following: A) An array of integers B) An integer that indicates the number of elements in the array The function should determine the mode of the array. That is, it should d ...

1 prove or show that the worst case time of the extraction

1. Prove or show that the worst case time of the extraction operation on a heap implemented as an array is O(log n). 2. Prove or show that the insertion and extraction operations on a heap implemented as a Python list is ...

Credit card number check the last digit of a credit card

Credit Card Number Check. The last digit of a credit card number is the check digit, which protects against transcription errors such as an error in a single digit or switching two digits. The following method is used to ...

Exercises for section 42in exercises 421 through 427 draw

EXERCISES for Section 4.2 In Exercises 4.2.1 through 4.2.7, draw the depth-first tree that results when Algorithm 4.2.1 is applied to the graph shown below, starting at the specified vertex. Include the dfnumbers and use ...

  • 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