Question

In: Computer Science

Consider the following languages: A = {w: |w| > k, where k is a constant integer}...

  1. Consider the following languages:
  • A = {w: |w| > k, where k is a constant integer}
  • B = {ε,0,1, 10, 001}
  • (The complement of A)
  • (The complement of B)
  1. (True/False)                    A is regular
  2. (True/False)                    B is regular
  3. (True/False)                     is regular
  4. (True/False)                      is regular  

2.  If A is regular, and  A  = A, then B must be not regular. True or False

3. Given three languages A, B, C where . If both A and B are regular, then C must be regular. True or False

Automata and Computation

Solutions

Expert Solution

2)if A is regular and B need not be regular.it depends on the language accepted by B

3)Even if both A and B are regular that doesn't mean C needs to be regular.it depends on the language generated by C.

So both 2 and 3 are false.

venereology answered 7 months ago
Next > < Previous

Related Solutions

Consider the two languages below: L1 = {w | w є {0,1,2}* and is of the...
Consider the two languages below: L1 = {w | w є {0,1,2}* and is of the form 0i1j2k where i, j and k ≥ 0 and i = j or j = k} L2 = {w | w є {0,1,2}* and is of the form 0i1j2k where i, j and k ≥ 0} One of the languages in the above problem is regular. Which one? Prove it. Prove that the OTHER one is not regular. Is the non-regular one context...
Consider the two languages below: L1 = {w | w є {0,1,2}* and is of the...
Consider the two languages below: L1 = {w | w є {0,1,2}* and is of the form 0i1j2k where i, j and k ≥ 0 and i = j or j = k} L2 = {w | w є {0,1,2}* and is of the form 0i1j2k where i, j and k ≥ 0} One of the languages in the above problem is regular. Which one? Prove it. Prove that the OTHER one is not regular. Is the non-regular one context...
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}.
Consider the velocity potential phi = -k( y^2 - x^2 ) where k is a constant....
Consider the velocity potential phi = -k( y^2 - x^2 ) where k is a constant. This velocity potential is commonly used to describe flow impinging upon a plate. Derive an equation for dP/dy, the pressure gradient in the y-direction, if the fluid has density, rho.
Consider two languages A and B where A is a context free language and B is...
Consider two languages A and B where A is a context free language and B is a regular language. Show that the set difference, A-B, must also be context free. Also show that B-A may not be context free
where k is a 11-bit integer variable. Show the largest possible range in decimal for k...
where k is a 11-bit integer variable. Show the largest possible range in decimal for k that will not cause any overflow in sign-magnitude, one's complement, two's complement and excess-1023 respectively. Each range should be shown as "[min,max]" (without the quotes). The ranges should be shown in the given order and separated by comma, for example, [-1,2],[3,4],[-5,6],[7,8].
A positive integer N is a power if it is of the form q^k, where q,...
A positive integer N is a power if it is of the form q^k, where q, k are positive integers and k > 1. Give an efficient algorithm that takes as input a number N and determines whether it is a square, that is, whether it can be written as q^2 for some positive integer q. What is the running time of your algorithm? write the pseudocode for the algorithm.
Consider the utility function U(W) = W^0.5 where W = wealth a) Perform the necessary calculations...
Consider the utility function U(W) = W^0.5 where W = wealth a) Perform the necessary calculations to demonstrate the order of preference of an investor with this utility function. Order them from most preferred to least preferred. -Prospect 1: 50% chance of $1000, 50% chance of $2000 -Prospect 2: 25% chance of $500, 25% chance of $2000, 50% chance of $1000 -Prospect 3: $1000 for certain. b) Explain the meaning of the expression certainty equivalent. (That is, Provide the definition)...
Given two languages A and B, let A/B denote the language {w | w x ∈...
Given two languages A and B, let A/B denote the language {w | w x ∈ A for some x ∈ B}. Show that if A is a context-free language and B is a regular language, then A/B is a context-free language. hint (construct PDAs)
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT