Question

In: Advanced Math

2. (CFGs) Give CFGs that generate the following languages. Use as few variables as you can...

2. (CFGs) Give CFGs that generate the following languages. Use as few variables as you can (and no more than requested). Unless specified otherwise, the alphabet is Σ = {0, 1}.

(c) L3 = {w | w represents a binary number that starts with 1 and is divisible by 3}. Use at most 4 variables.

(d) L4 = {x1#x2# · · · #xk | k ≥ 1, each xi ∈ {0, 1}* , and xi = xjR for some i != j}. Recall that wR represents string w written backwards. Use at most 4 variables.

Solutions

Expert Solution

Colby Messinger answered 5 months ago
Next > < Previous

Related Solutions

In many programming languages you can generate a random number between 1 and a limiting value...
In many programming languages you can generate a random number between 1 and a limiting value named LIMIT by using a statement similar to randomNumber = random(LIMIT). Create the logic for a guessing game in which the application generates a random number and the player tries to guess it. Display a message indicating whether the player’s guess was correct, too high, or too low. (After you finish Chapter 4, you will be able to modify the application so that the...
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}.
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...
Use the R script to finish the following operations: (1) Generate 60 normally distributed random variables...
Use the R script to finish the following operations: (1) Generate 60 normally distributed random variables with the mean 30 and the variance 16, and store them in the vector ‘rand.vec’. (2) Turn the vector ‘rand.vec’ into a 6X10 matrix, and assign the name ‘rand.mat’ to the matrix. (3) Given a normal distribution with the mean 30 and the variance 16, find the two values of x that contain the middle 50% of the normal curve area.
1.Give an advantage and a disadvantage of a parallel combination. Give an example. 2.Give a few...
1.Give an advantage and a disadvantage of a parallel combination. Give an example. 2.Give a few essential features of an ordinary cell. 3.How should two identical batteries be connected in order to obtain the maximum EMF from the combination, should it be in series or parallel? Why? ? 4.How does the resistance of a conductor affected by its length and diameter?
You can use any programming languages Using a random generator, compute 1000 integers between 1 and...
You can use any programming languages Using a random generator, compute 1000 integers between 1 and 1000. There will be duplicates in the array. Sort the array using bubble sort and merge sort. The two sorted arrays should agree. Then pick at random one element from your sorted array and use a binary search to find its position in the array.
Give a direct proof of the following theorem, upon which case you can use it for...
Give a direct proof of the following theorem, upon which case you can use it for future proofs. (Hint: note that we’ve called it a corollary as in p.81, not just a theorem.) Corollary 4.12. Every integer is even or odd.
Give a direct proof of the following theorem, upon which case you can use it for...
Give a direct proof of the following theorem, upon which case you can use it for future proofs. (Hint: note that we’ve called it a corollary as in p.81, not just a theorem.) Corollary 4.12. Every integer is even or odd.
Use the pumping lemma to prove that the following languages are not regular. (a)L2 = {y...
Use the pumping lemma to prove that the following languages are not regular. (a)L2 = {y = 10 × x | x and y are binary integers with no leading 0s, and y is two times x}. (The alphabet for this languages is {0, 1, ×, =}.) For example, 1010 = 10 × 101 is in L2, but 1010 = 10 × 1 is not. (b)Let Σ2 = {[ 0 0 ] , [ 0 1 ] , [ 1...
Use the Pumping Lemma to show that the following languages are not regular. (a) {ai bj...
Use the Pumping Lemma to show that the following languages are not regular. (a) {ai bj | i > j} (b) {apaq | for all integers p and q where q is a prime number and p is not prime}.
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT