Ask Question, Ask an Expert

+1-415-315-9853

info@mywordsolution.com

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}

Finally:

(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
to.]
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 explain the benefit of autoconfiguration2 explain the

1. Explain the benefit of autoconfiguration. 2. Explain the benefit of renumbering. 3. Which field in the IPv6 packet is responsible for multiplexing and demultiplexing?

1 design and implement an iterative version of the

1. Design and implement an iterative version of the factorial function. 2. Design and implement a recursive function for determining whether a string is a palindrome. A palindrome is a string of characters that is the sa ...

A printed circuit board can be modeled as a network of

A printed circuit board can be modeled as a network of pathways that either inerge into other paths as terminate into a node. Develop a vision system for isolating defects such as breaks (open circuits) and leaks (short ...

1 every country participating in the computer products

1. Every country participating in the computer products security evaluation has a list of evaluated products. Find out how to find this list. Does the ISO keep a global list of evaluated products? 2. Why is the product r ...

A food processing company makes meatloaf to be sold in the

A food processing company makes meatloaf to be sold in the frozen food section of supermarkets. Each week the recipe used changes based on the current cost of ingredients. Ingredients and current costs are as shown below ...

1 during 2003 we began to stop worrying that inflation was

1. During 2003, we began to stop worrying that inflation was a problem. Instead, we began to worry about deflation, a decline in the price level. Assume that the Fed decided to hold the money supply constant. What impact ...

Compare and contrast traditional outsourcing with the

Compare and contrast traditional outsourcing with the Software as a Service. Under what conditions do you think a company should choose SaaS over traditional outsourcing? Explain your views and discuss them with your pee ...

Implement a recursive algorithm to compute the n

Implement a recursive algorithm to compute the n! permutations of the first n integers. In your implementation, the internal recursive call should be of the form permutations (n -1) rather than permutations (k + 1) as we ...

Create 1 webpage that lays out the attached design using

Create 1 webpage that lays out the attached design using CSS. You may use any font you want.  You can get the pictures from the Word document by right clicking on each picture and choosing "Save as picture". Zip all your ...

A read hit occurs in way2 of set 17 within an 8-way set

A read hit occurs in way2 of set 17 within an 8-way set associative cache that uses a line size of 128 bytes. The total number of lines in the cache is 32768. The system employs 32-bit addresses and the tag for way2 with ...

  • 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