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 implement a new version of the sparse life grid adt from

1. Implement a new version of the Sparse Life Grid ADT from Chapter 4 to use a sorted list and the binary search to locate the occupied cells. 2. A colormap is a lookup table or color palette containing a limited set of ...

1 what is a work breakdown structure wbs is it the only way

1. What is a work breakdown structure (WBS)? Is it the only way to organize a project plan? 2. What is projectitis? How is it cured or its impact minimized? 3. List and define the common attributes of the tasks of a WBS.

Write a program that compares all four advanced sorting

Write a program that compares all four advanced sorting algorithms discussed in this chapter. To perform the tests, create a randomly generated array of 1,000 elements. What is the ranking of the algorithms? What happens ...

1 design and implement a program that compares the use of

1. Design and implement a program that compares the use of linear probing, quadratic probing, and double hashing on a collection of string keys of varying lengths. The program should extract a collection of strings from ...

Describe the facilitators role in a virtual team what tools

Describe the Facilitator's Role in a virtual team. What tools can a facilitator use to ensure High Impact Virtual Meeting? What are the keys to giving/ receiving constructive feedback? How is feedback different in a one- ...

1 can a router combine the advertisement of a link and a

1. Can a router combine the advertisement of a link and a network in a single link-state update? 2. Explain why we can have different intradomain routing protocols in different ASs, but we need only one interdomain routi ...

Your task is to design a general program for managing board

Your task is to design a general program for managing board games with two players. Your program should be flexible enough to handle games such as tic-tac-toe, chess, or the Game of Nim of Project 6.2. Design an interfac ...

Search the web for three different employee hiring and

Search the Web for three different employee hiring and termination policies. Review each and look carefully for inconsistencies. Do each of the policies have sections addressing information security requirements? What cl ...

In sect 1013 we state that sender or message authentication

In Sect. 10.1.3 we state that sender (or message) authentication always implies data integrity. Why? Is the opposite true too, i.e., does data integrity imply sender authentication? Justify both answers. In this exercise ...

Modify the current algorithm so that while it adheres to

Modify the current algorithm so that while it adheres to the basic template distribution idea, it does not add multiple extra spaces to a location before there has been one extra space added to each location.

  • 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