Use the pumping lemma to show that the following languages are not regular (c) (5 pts)...

Use the pumping lemma to show that the following languages are not regular

SUB = {x = y − z | x, y, z are binary integers, and x is the result of the subtraction of z from y}. For example: 1 = 1 − 0, 10 = 11 − 01 are strings in SUB but not 1 = 1 − 1 or 11 = 11 − 10.

Solutions

Expert Solution

Any queries just comment

Give thumbsup

Thank you and all the best

venereology answered 9 months ago

Next > < Previous

Related Solutions

Use the pumping lemma to show that the following languages are not regular. A a. A1={0^n...

Use the pumping lemma to show that the following languages are not regular. A a. A1={0^n 1^n 2^n | n≥0} b. A2 = {www | w ∈ {a,b}∗} A c. A3 ={a^2^n | n≥0} (Here, a^2^n means a string of 2^n a’s.) A ={a3n |n > 0 }

1. Pumping Lemma: a. Is the following language a regular language? (Use pumping lemma in proof.)...

1. Pumping Lemma: a. Is the following language a regular language? (Use pumping lemma in proof.) L = {0n 1n 2n | n ≥ 0} b. What is (i.e., define) the CFL pumping lemma?

Show that L2 = {anb2nan : n ≥ 0} is not context-free using the pumping lemma.

Determine whether or not the following languages are regular. If the language is regular then give...

Determine whether or not the following languages are regular. If the language is regular then give an NFA or regular expression for the language. Otherwise, use the pumping lemma for regular languages or closure properties to prove the language is not regular. 1) L = { 0 n1 k : k ≤ n ≤ 2k} 2) L = { 0 n1 k : n > 0, k > 0 } È { 1 k0 n : k > 0, n...

Are the following languages over {a, b} regular? If they are then prove it. If they...

Are the following languages over {a, b} regular? If they are then prove it. If they are not prove it with the Pumping Lemma a) {ap | p is a prime number} b) {xax | x Î{a,b}*} (start by listing some strings in, not in, the language

Formal Languages Give a regular expression for each of the following languages: L2a = {w ?...

Formal Languages Give a regular expression for each of the following languages: L2a = {w ? {0,1}* | w corresponds to the binary encoding of non-negative integers that are evenly divisible by 4 L2b = {w ? {a,b}* | w contains at least one 'a' and exactly two b's} L2c = {w ? {0, 1, 2}* | w starts with a 2, ends with a 1 and contains an even number of 0's}.

Use Myhill-Nerode Theorem to prove the following languages are not regular A1 = {0n1n2n| n >=...

Use Myhill-Nerode Theorem to prove the following languages are not regular A1 = {0n1n2n| n >= 0} A2 = {www| w E {a, b}*}

Describe the languages specified by the following regular expressions: 1. \$_+)/ 2. (\(740$...-...)|(...-...) (The alphabet is...

Describe the languages specified by the following regular expressions: 1. \$_+)/ 2. (\(740$...-...)|(...-...) (The alphabet is {1,2,3,4,5,6,7,8,9,0})

Mod 5(c) - CH 5 EXERCISES/PROBLEMS (31 pts) Hide or show questions eBook Calculator Print Item...

Mod 5(c) - CH 5 EXERCISES/PROBLEMS (31 pts) Hide or show questions eBook Calculator Print Item Ratio of Cash to Monthly Cash Expenses Kips Bay Medical Inc. is a medical device company that develops, produces, and sells products used in coronary surgery. The following data (in thousands) were adapted from recent financial statements. Year 4 Year 3 Year 2 Year 1 Operations: Net income (loss) $(5,607) $(6,060) $(5,507) $(4,250) Net cash flows from operating activities (5,026) (5,537) (4,203) (8,105) Balance...

Closure under Context-Free Languages Show that the following operations are closed under context-free languages: union concatentation...

Closure under Context-Free Languages Show that the following operations are closed under context-free languages: union concatentation Kleene star

Subjects