Question: EXERCISE 4 Show that {xcx | x e {a, *) is not regular. Hint: Copy the proof ofTheorem 11.2- only minor alterations are needed Theorem

EXERCISE 4 Show that {xcx" | x e {a, *) is

EXERCISE 4 Show that {xcx" | x e {a, *) is not regular. Hint: Copy the proof ofTheorem 11.2- only minor alterations are needed Theorem 11.2: x is not regular for any alphabet with at least two symbols Proof: Let M2(Q, , 8, %, F) be any DFA with 1 1 2; we will show that L(M) {xx/J. The alphabet contains at least two symbols; call two of these a and b. Consider the behavior of M on an arbitrarily long string of as. As it reads the string, M visits a sequence of states: first "(%-c), then *(%-a), then "(%-aa), and so on. Eventually, since M has only finitely many states, it must revisit a state; that is, there must be some i and j with i

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!

Prove that { a n b * c n } is not regular. Hint: Copy the proof of Theorem 11.1only minor alterations are needed. Theorem 11.1: la"b"g is not regular. Proof: Let M= (Q {a, b}, , q0, F) be any DFA...

In this question you will be asked to reflect on a project you have been involved in or observed, in which a design evolved, or could have evolved, through applying a theory of user behaviour. You...

HW 12, MAT 312/AMS 351: SPRING 2017 Problem 1. (1) Set H = {4a + 6b | a, b Z} Z. Show that H is a subgroup of Z. (2) Is H cyclic? Problem 2. Write down all the cyclic subgroups of the following...

Consider the trigonometric series a0 2 + X r=1 (ar cos rx + br sin rx) where a0, a1, a2, . . . and b1, b2, . . . are constants and suppose that f(x) is a periodic function of x with period 2. (a)...

In a Hopfield neural network configured as an associative memory, with all of its weights trained and fixed, what three possible behaviours may occur over time in configuration space as the net...

Let A, B be sets. Define: (a) the Cartesian product (A B) (b) the set of relations R between A and B (c) the identity relation A on the set A [3 marks] Suppose S, T are relations between A and B, and...

for 1552474 Lic48000040179 S ZI PER 31 Uniform Residential Appraisal Report The purpose s summary appraisal report is to provide the lender der with an and d y sporiadanion of the market value of the...

A discrete sequence {xn} can be converted into a continuous representation x(t) = ts X n= (t n ts) xn, where ts is the sampling period. (a) State two characteristic properties of Dirac's function. [2...

Proofs Self-Assessment Instructions Instructions: These problems are provided for your own self-assessment. You need to work on them alone, solve them without looking at the solution, and only then...

You are Jane a call centre manager for an insurance company, MCI Insurance Ltd. MCI Insurance has been operating for over 15 years. MCI Insurance specialises in car, households, and contents...

THE LEGAL ENVIRONMENT DIMENSION At Brieres stable, LaPlace had access to, and control over, Park Me In First at any time. Could Briere thus deny that a bailment relationship existed? Explain. WHAT IF...

The cumblative feabure of preferred stock requires that dividends not paid in any year munt be paid in a later year belone dividench are dintributed te common shareholders. imis the cumb athe...

Which of the following are problems with identifying users of ABC? Multiple select question. ABC means different things to different organizations. Organizations will announce the discontinuance of...

2 How does adversity inspire public speaking and, indeed, public life? In American culture, what defines a public figure?

Have you ever attended a speaking event where the speaker did not behave appropriately for the occasion? How did it make you feel as a listener?

4 Is a shooting victim or the family of that victim more credible on the issue of gun control than someone whose life has not been touched by gun violence?