The first five questions give languages over {0, 1}. In each case decide whether the language...

The first five questions give languages over {0, 1}. In each case decide whether the language is regular or not, and prove your answer is correct.

5. The set of strings in which the number of 0's is a perfect square.

Solutions

Expert Solution

The given language is not regular. Use the pumping lemma for regular langauges to prove this.

Let the pumping length be . Consider the word which is in L as the number of 0s is a perfect square. Now consider any breakup of the word . Then as w consists of only 0s, y must also consists of only 0s, hence where the bound on length of y come from the bound on the length of xy.

Now consider the pumped up word . Then as per the bounds for i, it gives that . Note that this automatically means . Now consider . This implies . Hence is between two consecutive perfect squares and doesn't equal either of them. This implies that it cannot be equal to any perfect square, proving that .

Therefore the language doesn't satisfy the pumpign lemma for regular langauge, hence it is not regular. Comment in case of any doubts.

venereology answered 1 month ago

Next > < Previous

Related Solutions

The first five questions give languages over {0,1}. In each case decide whether the language is...

The first five questions give languages over {0,1}. In each case decide whether the language is regular or not, and prove your answer is correct The set of all strings x beginning with a non-null string of the form ww.

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...

Consider the following languages over {0, 1}: L3 = {w : does not begin and end...

Consider the following languages over {0, 1}: L3 = {w : does not begin and end with same symbol and |w| £ 3} L4 = {w : w = wR, |w| £ 3} Enumerate the first 8 strings in the L-ordering of the following: L3 L4 L3 – L4 L4 – L3 L3L4 L4L3 L33 L4*

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}.

For each of the questions below, a histogram is described. Indicate in each case whether, in...

For each of the questions below, a histogram is described. Indicate in each case whether, in view of the Central Limit Theorem, you can be confident that the histogram would look like approximately a bell-shaped (normal) curve, and give a brief explanation why (one sentence is probably sufficient). There are no data for these questions, so you will not need to use the computer to answer these questions. A police department records the number of 911 calls made each day...

For each of the questions below, a histogram is described. Indicate in each case whether, in...

For each of the questions below, a histogram is described. Indicate in each case whether, in view of the Central Limit Theorem, you can be confident that the histogram would look like approximately a bell-shaped (normal) curve, and give a brief explanation why (one sentence is probably sufficient). 1. The price of one gallon of gasoline at a particular gas station is recorded every day of the year, and the 365 values are plotted in a histogram. 2. Two hundred...

For each system listed in the first column of the table below, decide whether the change...

For each system listed in the first column of the table below, decide whether the change described in the second column will increase the entropy S of the system, decrease, or leave S unchanged. If you don’t have enough information to deiced, check the “not enough information” button in the last column System Change ϫS A few moles of carbon CO2 gas The carbon dioxide is cooled from -2 C to -9 Cwhile the volume is held constant at 10...

Give a grammar that generates each of the following languages: (1) L = {a2n cm bm...

Give a grammar that generates each of the following languages: (1) L = {a2n cm bm | m ≥ 0, n ≥ 0} (2) L = {an b2m cn | m ≥ 0, n ≥ 0} (3) L = {an bm | n+m is even} (4) L = {an bm | n ≤ m+3} (5) The complement of the language L = {anbn | n ≥ 0}

Give examples of languages L1 and L2 over {a, b} that satisfy the descriptions below: (a)...

Give examples of languages L1 and L2 over {a, b} that satisfy the descriptions below: (a) L1 is regular, L2 is nonregular, and L1 U L2 is regular; (b) L1 is regular, L2 is nonregular, and L1 U L2 is nonregular; (c) L1 is regular, L2 is nonregular, and L1 n L2 is regular; (d) L1 is nonregular, L2 is nonregular, and L1 U L2 is regular. (e) L1 is nonregular, L2 is nonregular, and L1 n L2 is regular.

Determine if the language ?={?^?∶?=?^3????????≥0}over Σ={?}is regular.

Subjects