(a) write a regular expression for the language A of binary strings whose length is divisible by three

(b) the language B of all binary strings that do not contain two consecutive 1's.

Where would I start?

Deromediqm
2022-07-17
Answered

For example lets say you were trying to

(a) write a regular expression for the language A of binary strings whose length is divisible by three

(b) the language B of all binary strings that do not contain two consecutive 1's.

Where would I start?

(a) write a regular expression for the language A of binary strings whose length is divisible by three

(b) the language B of all binary strings that do not contain two consecutive 1's.

Where would I start?

You can still ask an expert for help

Kitamiliseakekw

Answered 2022-07-18
Author has **23** answers

Step 1

One very straightforward approach to (a) is to begin by listing the 8 binary strings of length 3. Every string whose length is a multiple of 3 must be formed by concatenating those strings. I’ll illustrate with strings of even length: any string of even length can be segmented into two-character chunks, each of which must be 00,01,10, or 11, so the binary strings of even length are described by the regular expression $(00+01+10+11{)}^{\ast}$. (You may use some other symbol than + to indicate alternatives; common alternatives are ∣, $\vee $, and $\cup $.)

Step 2

Problem (b) is a little harder. The condition says that if a string contains a 1 at all, that 1 must either be the last symbol in the string or be followed immediately by a 0. Ignore for a moment the exceptional case of a final 1; if we just require that every 1 be followed immediately by a 0, we’re allowing precisely those strings that can be built by concatenating 0’s and 10’s, i.e., the strings described by the regular expression $(0+10{)}^{\ast}$. We’d like to have all of those strings, but also all strings that consist of one of those followed by a single 1; how can you modify or extend the regular expression to include the latter type as well as the former?

One very straightforward approach to (a) is to begin by listing the 8 binary strings of length 3. Every string whose length is a multiple of 3 must be formed by concatenating those strings. I’ll illustrate with strings of even length: any string of even length can be segmented into two-character chunks, each of which must be 00,01,10, or 11, so the binary strings of even length are described by the regular expression $(00+01+10+11{)}^{\ast}$. (You may use some other symbol than + to indicate alternatives; common alternatives are ∣, $\vee $, and $\cup $.)

Step 2

Problem (b) is a little harder. The condition says that if a string contains a 1 at all, that 1 must either be the last symbol in the string or be followed immediately by a 0. Ignore for a moment the exceptional case of a final 1; if we just require that every 1 be followed immediately by a 0, we’re allowing precisely those strings that can be built by concatenating 0’s and 10’s, i.e., the strings described by the regular expression $(0+10{)}^{\ast}$. We’d like to have all of those strings, but also all strings that consist of one of those followed by a single 1; how can you modify or extend the regular expression to include the latter type as well as the former?

asked 2021-08-15

How many elements are in the set
{ 0, { { 0 } }?

asked 2021-08-18

Discrete Mathematics Basics

1) Find out if the relation R is transitive, symmetric, antisymmetric, or reflexive on the set of all web pages.where $(a,b)\in R$ if and only if

I)Web page a has been accessed by everyone who has also accessed Web page b.

II) Both Web page a and Web page b lack any shared links.

III) Web pages a and b both have at least one shared link.

asked 2020-11-09

Use proof by Contradiction to prove that the sum of an irrational number and a rational number is irrational.

asked 2021-07-28

Let A, B, and C be sets. Show that

asked 2022-07-03

How many 2021-digit numbers can be formed from 1, 2, 3, 4, 5 and is divisible by 3 (possible repetition).

So i have one approach to the problem. I used pigeon hole theorem to prove that there are at least $[\frac{2021}{5}]+1=405$ identical number. And since 405 is divisible by 3 so the sum of those 405 same digit is also divisible by 3 and i only need to solve the problem with $2021-405=1616$-digit numbers. I continued that until there is less than 3 identical digit (the number of identical digits must be divisible by 3). At that point, the problem can be converted to

How many 8-digit numbers can be formed from 1, 2, 3, 4, 5 and is divisible by 3 (possible repetition).

To solve the above problem, i tried to find all 3x for $5\ast 1\le 3x\le 5\ast 5$ and solve every custom sub-problem. But my solution seems to be too tedious and i wonder if there is a specific formula to solve the first problem. Every idea is appreciated. Thanks in advance.

I also want to know if there is a way to solve this problem

Share m candy bars to n people such that no one have more than k candy bars.

That sub-problem can help solve my problem.

So i have one approach to the problem. I used pigeon hole theorem to prove that there are at least $[\frac{2021}{5}]+1=405$ identical number. And since 405 is divisible by 3 so the sum of those 405 same digit is also divisible by 3 and i only need to solve the problem with $2021-405=1616$-digit numbers. I continued that until there is less than 3 identical digit (the number of identical digits must be divisible by 3). At that point, the problem can be converted to

How many 8-digit numbers can be formed from 1, 2, 3, 4, 5 and is divisible by 3 (possible repetition).

To solve the above problem, i tried to find all 3x for $5\ast 1\le 3x\le 5\ast 5$ and solve every custom sub-problem. But my solution seems to be too tedious and i wonder if there is a specific formula to solve the first problem. Every idea is appreciated. Thanks in advance.

I also want to know if there is a way to solve this problem

Share m candy bars to n people such that no one have more than k candy bars.

That sub-problem can help solve my problem.

asked 2021-01-31

Use symbols to write the logical form of the following arguments. If valid, iden-
tify the rule of inference that guarantees its validity. Otherwise, state whether the
converse or the inverse error has been made.
If you study hard for your discrete math final you will get an A.
Jane got an A on her discrete math final.
‘Therefore, Jane must have studied hard.

asked 2022-07-03

Prove if a relation is left-total and right-unique

In this exercise, we are dealing with Tuple sets.

So let $M\subset P(A\times \mathbb{N})$ be the set of all legal tuple sets. P (X) denotes the power set of a set X. Now, Let the tuple set operation be defined as $+$ so that $+$: $M\times M\to M$.

Prove or disprove that + is left-total and right-unique.

These types of relations are uncommon in English, it seems. So, it's a bit difficult for me to understand how to prove it.

To my knowledge, a left-total relation means that, e.g. if $\mathrm{\forall}x\in A$ $\mathrm{\exists}y\in N$ $(x,y)\in M$, i.e. for every $x\in A$ there exists (at least) one $y\in N$, so that $(x,y)\in M$.

In this exercise, we are dealing with Tuple sets.

So let $M\subset P(A\times \mathbb{N})$ be the set of all legal tuple sets. P (X) denotes the power set of a set X. Now, Let the tuple set operation be defined as $+$ so that $+$: $M\times M\to M$.

Prove or disprove that + is left-total and right-unique.

These types of relations are uncommon in English, it seems. So, it's a bit difficult for me to understand how to prove it.

To my knowledge, a left-total relation means that, e.g. if $\mathrm{\forall}x\in A$ $\mathrm{\exists}y\in N$ $(x,y)\in M$, i.e. for every $x\in A$ there exists (at least) one $y\in N$, so that $(x,y)\in M$.