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

Examine the fixture assembly figure 2066 on page 1033 look

Examine the FIXTURE ASSEMBLY (Figure 20.66) on page 1033. Look at the relationships between the END PLATES (part 3) and the other parts in the assembly. Follow the Five-Step GDT Process to completely dimension and tolera ...

These exercises consider data from the 2005-2006 nhanes the

These exercises consider data from the 2005-2006 NHANES. The objective of this set of exercises is to perform a typical imputation and analysis session. The logical steps include examination of missing data, imputation o ...

Scenario your system was running fine but you occasionally

Scenario: Your system was running fine, but you occasionally notice the sound output was "glitchy" and you decide to add a sound card. As luck would have it, a friend gave you his old sound card from a system he threw aw ...

In iterative projects find out how project closure is

In iterative projects, find out how project closure is different compared to project closure in traditional projects. What are typical project tasks in project closure phase?

Assume that you are a judge for the malcolm baldrige award

Assume that you are a judge for the Malcolm Baldrige Award. Using Table 8.4 on in your text, how would you evaluate Crocs' for this prestigious award? Briefly describe the Baldrige Award. State each category of evaluatio ...

Consider the following tablea write sql statements to

Consider the following table: A. Write SQL statements to display the values of any rows that violate these functional dependencies B. If no data violate these functional dependencies, can we assume that they are valid? W ...

Toys galore currently has a credit limit of 7500 because

Toys Galore currently has a credit limit of $7,500. Because Toys Galore has an excellent credit rating, TAL Distributors is increasing the company's credit limit to $10,000. If you run the SQL query in Question 2b after ...

Suppose you are a data administrator for a large european

Suppose you are a data administrator for a large European pharmaceutical manufacturer that has significant sales and marketing efforts in Europe, Japan, and the United States. What data management issues would you have t ...

1 define what the project management framework is and

1) Define what the project management framework is and explain what pieces make up the framework. What are the processes and framework? What is the purpose of having a framework? Note: The answer should be between 500 to ...

Ensure a safe workplaceq1 what methods can be used to

Ensure a safe workplace Q.1 What methods can be used to facilitate consultation and participation? Discuss in 100-120 words Q.2 Explain (100-120 words) the barriers you think might prevent effective communication of heal ...

  • 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

A cola-dispensing machine is set to dispense 9 ounces of

A cola-dispensing machine is set to dispense 9 ounces of cola per cup, with a standard deviation of 1.0 ounce. The manuf

What is marketingbullwhat is marketing think back to your

What is Marketing? • "What is marketing"? Think back to your impressions before you started this class versus how you

Question -your client david smith runs a small it

QUESTION - Your client, David Smith runs a small IT consulting business specialising in computer software and techno

Inspection of a random sample of 22 aircraft showed that 15

Inspection of a random sample of 22 aircraft showed that 15 needed repairs to fix a wiring problem that might compromise

Effective hrmquestionhow can an effective hrm system help

Effective HRM Question How can an effective HRM system help facilitate the achievement of an organization's strate