Which of the following languages are regular?A = {x | x has two 0’s separated by the number of positions that is a multiple of 4 }.B = {x | x is binary representation of multiple of 3}.C = {x | x is a binary string and decimal of any prefix of x is not of form 3m + 2, where m ≥ 0}.Select one:a. All of the mentioned.b. Only B and C. c. Only A.d. Only B.
Question
Which of the following languages are regular?A = {x | x has two 0’s separated by the number of positions that is a multiple of 4 }.B = {x | x is binary representation of multiple of 3}.C = {x | x is a binary string and decimal of any prefix of x is not of form 3m + 2, where m ≥ 0}.Select one:a. All of the mentioned.b. Only B and C. c. Only A.d. Only B.
Solution
The answer is b. Only B and C.
Here's why:
A = {x | x has two 0’s separated by the number of positions that is a multiple of 4 }. This language is not regular because it requires memory of the position of the '0's in the string, which a finite automaton (the theoretical machine that recognizes regular languages) cannot do.
B = {x | x is binary representation of multiple of 3}. This language is regular. You can construct a finite automaton that accepts binary strings that represent multiples of 3.
C = {x | x is a binary string and decimal of any prefix of x is not of form 3m + 2, where m ≥ 0}. This language is also regular. You can construct a finite automaton that accepts binary strings where the decimal representation of any prefix is not of the form 3m + 2.
So, the answer is b. Only B and C.
Similar Questions
Which of the following is a regular language?
Which language accepted by the regular expression (0+1)*0(0+1)*0(0+1)*.Select one:a. The set of all strings containing at least two 0’s.b. The set of all strings that begin and end with either 0 or 1.c. The set of all strings containing at most two 0’s.d. The set of all strings containing the substring 00.
For each of the following languages over the alphabet Σ = {a, b, c} specified by the regular expressions (a)–(c),provide two strings in Σ∗ that are members and two strings in Σ∗ that are not members of the language (fourstrings each).(a) ab + a(b) ((bc)∗ + b)a(c) (a + ab + abc)∗(b + c)
Which of the following is a Regular Language?~L={a^n b^ n |n>=0} =L={a^n b^ n |0=5}Select one:a. 1b. Lc. {a^n b^ n |n>
For each of the following languages, determine whether it is regular or not, and give a proof. To prove that a language is not regular, you should use the fooling set method. (To prove that a language is regular, you are allowed to use known facts about regular languages, e.g., closure properties, all finite languages are regular, . . . ) (a) {0 i1 j0 k : j is divisible by i + k, and i + j + k is divisible by 4, and i, j, k ≥ 5}.
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.