Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

Consider the language L = {(aa)^m c(bb)^n: m, n greaterthanorequalto 0}. This language contains the strings c, aacbb, aaaacbb, et cetera. Consider the following theorem

image text in transcribed

Consider the language L = {(aa)^m c(bb)^n: m, n greaterthanorequalto 0}. This language contains the strings c, aacbb, aaaacbb, et cetera. Consider the following theorem and proof: Theorem: L is regular. Proof: We show that in the regular expression game, A (the opponent) can always win. Suppose A picks the integer N 50, B picks any string (aa)^m c(bb)^n of length larger than 50, then if m greaterthanorequalto 1 A picks x = e, y = aa, z = (aa)^m-1 c(bb)^n. Now whatever Value of i B picks, the string xy^iz is in L because xy^iz is (aa)^i (aa)^m-1 c(bb)^n. If m = 0 then (because the string has length larger than 50), n greaterthanorequalto 1 and A picks x = c, y = bb, and z = (bb)^n-1. This is possible because n greaterthanorequalto 1. Whatever value of i B picks, the string xy^iz is in L because xy^iz is c (bb)^i (bb)^n-1. Therefore the opponent (A) can always win, so L is not regular. Is the theorem correct? Is the proof correct? Justify both of your answers. Consider the language L = {(aa)^m c(bb)^n: m, n greaterthanorequalto 0}. This language contains the strings c, aacbb, aaaacbb, et cetera. Consider the following theorem and proof: Theorem: L is regular. Proof: We show that in the regular expression game, A (the opponent) can always win. Suppose A picks the integer N 50, B picks any string (aa)^m c(bb)^n of length larger than 50, then if m greaterthanorequalto 1 A picks x = e, y = aa, z = (aa)^m-1 c(bb)^n. Now whatever Value of i B picks, the string xy^iz is in L because xy^iz is (aa)^i (aa)^m-1 c(bb)^n. If m = 0 then (because the string has length larger than 50), n greaterthanorequalto 1 and A picks x = c, y = bb, and z = (bb)^n-1. This is possible because n greaterthanorequalto 1. Whatever value of i B picks, the string xy^iz is in L because xy^iz is c (bb)^i (bb)^n-1. Therefore the opponent (A) can always win, so L is not regular. Is the theorem correct? Is the proof correct? Justify both of your answers

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Strategic Database Technology Management For The Year 2000

Authors: Alan Simon

1st Edition

155860264X, 978-1558602649

Students also viewed these Databases questions

Question

2. Do you find change a. invigorating? b. stressful? _______

Answered: 1 week ago

Question

10. Are you a. a leader? b. a follower? _______

Answered: 1 week ago