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

Assignment employee trainingcontinuing with the paper

Assignment: Employee Training Continuing with the paper developed in Weeks One, Two, and Three, add an additional 2 to 3 pages (700 to 1,050 words) describing your plans for training employees and preparing them for syst ...

1 which signal has a wider bandwidth a sine wave with a

1. Which signal has a wider bandwidth, a sine wave with a frequency of 100 Hzvb or a sine wave with a frequency of 200 Hz? 2. What is the bit rate for each of the following signals? a. A signal in which 1 bit lasts 0.001 ...

1 when looking at the chronology of the development of the

1) When looking at the chronology of the development of the Internet, which development do you believe to be the most important? Why? 2) In terms of online users, are the genders equally represented? How about for minori ...

1 mapleland is considering expanding the mfn to include

1. Mapleland is considering expanding the MFN to include wireless access for its residences. What additional investigation will you do to prepare for a citywide wireless network? 2. What security concerns do you have for ...

1 in your own words describe the two motivations for

1. In your own words, describe the two motivations for defining functions in your programs. 2. We have been thinking about computer programs as sequences of instructions where the computer methodically executes one instr ...

1 what common security system is an idps most like in what

1. What common security system is an IDPS most like? In what ways are these systems similar? 2. How does a false positive alarm differ from a false negative one? From a security perspective, which is least desirable? 3. ...

1 investigate how netscape navigator and internet explorer

1. Investigate how Netscape Navigator and Internet Explorer implemented SSL technology. 2. Study both SSL and S-HTTP. Show that these two protocols have a lot in common. However, the two protocols have some differences. ...

Create and test a set class to represent a classical set

Create and test a Set class to represent a classical set. Your sets should support the following methods: Set(elements) Create a set (elements is the initial list of items in the set). addElement(x) Adds x to the set. de ...

1nbsptcos 3 and 5 in windows 7 how do you open the task

1.  (TCOs 3 and 5) In Windows 7, how do you open the Task Manager? On the Processes tab, name, and describe at least three parameters that are displayed by default. Should be at least one paragraph

Assignmentyou are working for a retirement planners company

Assignment You are working for a Retirement Planners company that helps customers plan retirement parties. The company has to track all retirement parties for which it is providing planning services. However, since you a ...

  • 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