Question: Consider the following invalid proof that A cup { epsi } is regular if A is regular: Since A is regular, it has

Consider the following invalid proof that A \cup {\epsi } is regular if A is regular:
Since A is regular, it has a NFA N. We can create an NFA N for A \cup {\epsi }, modifying N by setting the start state to be accepting. Then N accepts A\cup {\epsi }, Q.E.D.
Show that this proof is invalid by giving a regular language A and an NFA N for A, such that constructing N as described in the proof does not accept A\cup {\epsi }.

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!

Q:

Let L be a finite language. Consider the following invalid proof that L is infinite: (a) Since L is finite, it is regular. (b) Since L is regular, the pumping lemma applies to L. (c) There is a...

Q:

Theory of Computation Activity Consider the following incorrect proof that following language is not regular. D= {w | W {a,b}* and the length of w is odd } (attempted) Proof: (a) Suppose that D is a...

Q:

2 . What is the power set of S = { } ? 3 . [ 2 marks ] Consider a set S with n elements. For what values of n ( if any ) , does S \ times S have the same number of elements as the power set of S ? 4...

Q:

Let r and s be solutions to the quadratic equation x 2 b x + c = 0. For n N, define d0 = 0 d1 = r s dn = b dn1 c dn2 (n 2) Prove that dn = r n s n for all n N. [4 marks] (b) Recall that a commutative...

Q:

7 . Find two errors in the following attempted formal definition of a finite automaton: Q: a set of states \ Sigma : a finite input alphabet \ delta : Q \ times \ Sigma - > Q q 0 in \ Sigma F Q 1 8 ....

Q:

For two binary strings x, y epsilon {0, 1}*, of the same length, their Hamming distance d_H(x, y) is the number of bits in which they differ. For example d_H(1111, 1111) = 0, d_H(0001, 1111) = 3, and...

Q:

re Regular Languages and Finite Automata (a) Let L be the set of all strings over the alphabet {a, b} that end in a and do not contain the substring bb. Describe a deterministic finite automaton...

Q:

answer the question clearly You are building a flight-control system for which a convincing safety case must be made. Would you assign the tasks of safety requirements engineering, test case...

Q:

ret Electricity consumers are supplied with electricity from an electricity generating station. Electricity is distributed from the station to the various consumers through a network of transformers...

Q:

From the case study identify no less than five difficulties and traps mentioned by the case study authors. Please select three areas essential to project management success. Explain why you selected...

Q:

The orsat analysis of the excesses gases from a diesel engine using hydrocarbon fuel is given CO2 8.2%; 01 9.8%; CO 0.85%. Calculate (1) Fuel air ratio (2) mass analysis of fuel.

Q:

Using the sample results in Exercise 10.71, construct and interpret the 90% confidence interval for the population proportion. Is the hypothesized population proportion (0.07) within the interval?...

Q:

A credit union entered a lease contract valued at $ 6 9 0 0 . The contract provides for payments at the end of each quarter for 3 years. If interest is 4 . 5 % compounded quarterly , what is the size...

Q:

Pls use codeblocks software to do the codiing for the program. Thanks a lot for the help. As an engineer, you are required to propose and design a project based on complex engineering problem using C...