## Regular Expression with at least one a, even number of b

I’ve been working on some regular expression questions, and came across one that I cannot figure out. Working on the language over $$\{a, b\}$$, the text asks for a regular expression for the language of all words having at least one a and an even number of b’s, using only | and * (maybe $$\varepsilon$$ too). My idea so far has been something like $$(a^*ba^*b)^*a^*a(a^*ba^*b)^*a^*$$, but this doesn’t match cases like bab, bbbab, or baaab.

## Grouping n points into groups of size m with objective to have least traveling distance in each group

Assumptions:

• There are “n” jobs which are distributed over the city.
• Company has “k” available workers.
• Each worker can do “x” jobs per day.
• “x” is dependent to the worker skills and the distance he travels each day so it’s not a constant.
• Workers have no initial traveling distance.
• “s” is a set that shows each workers can do how many jobs based on the distance he travels
• “d” is the number of days that takes for company to do all the jobs.

Objective: Minimize the “d”

I know this problem is probably NP-hard so I don’t need the exact answer. I think it’s kinda a variation of Traveling salesman problem combining with scheduling and assignment problems.

My algorithm for this problem is to “some how” efficiently ( of course not the most efficient way ) grouping the jobs based on their traveling distance in the groups in to groups of “m” which is the mean of set “s”. Then after each day rerun the algorithm to get better results.

My question is what is the best way to do that grouping? Anyway if you know a better algorithm I would be more than happy to know them.

## How can I bring a creature back to life 5 times per long rest with the least investment of levels?

Very related: How can I bring a lowly terrestrial invertebrate back to life 5 times per long rest with the least investment of levels?

A character wants to proactively use the Chronicle of the Raven Queen eldritch invocation (from UA: Warlock & Wizard) but must respect the Law of Death — that creatures should be dead when it is ‘their time’ and not otherwise. To satisfy this, the character must ensure that the creatures they ‘question’ are dead for not very much longer than is strictly necessary for the invocation to work. Specifically, the character must end each day with no creature they killed merely for questioning still dead as a result of said killing.

Nevertheless, the character is committed to using the invocation proactively on creatures that they would not otherwise have killed, 5 times per long rest.

What is the least number of levels for such a character to be possible? Assume magic items are gained with levels at the normal rate, and that those items are whatever is most helpful to the build. If you need any mundane items, monies, or things purchasable with money, you should assume the character has an average amount of money from hoards for their level as well as close to the median amount of individual monster treasure. Remember that the character has to have at least three levels in Warlock (the invocation requires the Pact of the Tome), so you can’t e.g. be an 18th-level Rogue (not that that would necessarily solve the problem, just as an example).

Multiclassing and UA are okay, as well as any other first-party sources.

## How can I bring an insect back to life 5 times per long rest with the least investment of levels?

I wanna use the Chronicle of the Raven Queen invocation but I don’t wanna leave all the cockroaches, silverfish, and hydrazoa I interrogate dead afterwards (I realize I could take Beast Speach instead, but I don’t wanna). What do I need to multiclass and for how many levels to be able to bring the insects I question back to life after I kill them? They don’t need to be dead for more than a single round.

I want to do this ASAP in terms of levels. 4 levels of Warlock with the Pact of the Tome, the Raven Queen patron, and the Chronicle of the Raven Queen invocation are non-negotiable. Everything else (including race and background, if needed) is available. Magic Items are fine, but be aware of the levels required before I can likely get the party to track one down: Uncommon or Common magic items will be trivial to track down, but a rare item will take me about 5 levels, a very rare 11, and a legendary 14. Consumables are also okay, but I’m only getting like 1 per level on average and getting a legendary consumable isn’t very likely to ever happen before I’m already 20th level.

## What’s the least signifcant bit of a mantissa system?

If Mantissa is a 1-dot-M fixed-point number whose most significant bit is always 1 then, how is the least significant bit calculated?

I know the least and most significant bit of the mantissa results in the following range:

1.0 <_ Mantissa <_ (2.0 - 1/2^M) 

But specifically, I don’t understand where the 2 comes from.

## Pushdown Automata – constructing a PDA to recognise a language with at least as many as as bs

I am trying to construct a 3-state PDA to recognise (I need to create a transition diagram for this question)

W = {w ∈ {a, b}^* | w contains at least as many as as bs} 

My thought process so far has been this:

 1. Start off in q0 (q0 being an accept state)  2. add a $to the start of the stack (so you can see when the stack is empty), then transition to q1 (not an accept state). 3. If you receive an a: - if there is an a at the top of the stack, push the a on. - if there is a b at the top of the stack, pop the b. - if there is nothing on the top of the stack, push the a on. 4. If you receive a b: - if there is an a at the top of the stack, pop the a. - if there is a b at the top of the stack, push the b on. - if there is nothing on the top of the stack push the b on. 5. Once there is no more input: - if there is a$   at the top of the stack, transition to q3 (q3 being an accept state) - this means there was an equal number of as and bs   - if there is an a at the top of the stack, transition to q3 (q3 being an accept state) - this means there was more as than bs   if there is a b at the top of the stack, it means there was more bs than as, and thus we stay in q2, which is not an accept state. 

(Sorry if this is hard to understand, I am not sure how to link those transition diagrams of the PDA’s I’ve seen in some posts, if someone can tell me how to create one and link it in the post, I can update the post to be more understandable if needed)

I have a few questions:

1. Is this approach correct?
2. Is the it correct to assume the machine is smart enough to know that if there isn’t a b at the top of the stack, and I receive an a, it will push that a onto the stack (something like (q1, a, ε) -> (q1, a) to cover both cases where there is an a on the top of the stack and also the case where the stack has nothing in it))
3. Do I need to push a $at the start from q0 to q1 in the transition diagram (I’ve seen this to be the case for all PDAs on my lecture slide – which makes me think is it necessary to include if all machines need to do this – why is it not just implied?) 4. I am ok to have 2 different scenarios to go to q2 right? Or would I be better doing something in q1, where if I have reached the end of my input queue, keep popping off as on the top of the stack until I reach the$ , then transition to q2?

Sorry if anything is unclear – I am not super familiar with PDAs and the way to describe things – please let me know if I need to clarify anything.

## Return the smallest subset of an array whose elements sum to at least given value

Suppose we are given an array A[1..n] and a value C.

Does there exist an algorithm with linear expected run time that can produce an array that is the smallest subset of A[1..n] whose elements sum to at least C?

## Tuple Relational Calculus – Find names of persons who own at least one house in each city in Canada

Using tuple relational calculus, Find names of persons who own at least one house in each city in Canada.

Bolded are keys.

City(city-name,country-name,area,population)

House(hno,#rooms,stno,owner-name)

Street(stno,city-name,length)

This is what I came up with:

{ h.owner-name | House(h) and forAll c (City(c) and c.name=”Canada”) -> (Exists s(Street(s) and s.city-name = c.name) and Exists x(House(x) and x.stno = s.stno and x.owner-name = h.owner-name) ) }

How I read this aloud: “For all Canadian cities, there exists a street with a HOUSE x that has the same owner as the HOUSE h.”

Is this correct? I’ve peen pulling my hair out trying to understand tuple relational calculus.

## How could I block or at least detect the use of ultrasonic side channels or Google Nearby Messages API on my smartphone?

My question is about the use of ultrasonic messages that are part of the modern advertising ecosystem and are also used by the Google Nearby Messages API.

When it comes to advertising, the type of ultrasonic messages that I am referring to are described in this Wired article titled “How to Block the Ultrasonic Signals You Didn’t Know Were Tracking You”, from 2016. The article says (emphasis added):

The technology, called ultrasonic cross-device tracking, embeds high-frequency tones that are inaudible to humans in advertisements, web pages, and even physical locations like retail stores. These ultrasound “beacons” emit their audio sequences with speakers, and almost any device microphone—like those accessed by an app on a smartphone or tablet—can detect the signal and start to put together a picture of what ads you’ve seen, what sites you’ve perused, and even where you’ve been.

The Wired article also mentions that:

Now that you’re sufficiently concerned, the good news is that at the Black Hat Europe security conference on Thursday, a group based at University of California, Santa Barbara will present an Android patch and a Chrome extension that give consumers more control over the transmission and receipt of ultrasonic pitches on their devices.

Being that the article was from 2016, I looked at the Black Hat Europe conference from that year for more information about the Android patch. The presentation mentioned in the Wired article seems to be this one.

The presentation slides (available here) led me to the ubeacsec.org website where the researchers do have an android patch as mentioned in the Wired article. Alas that patch is a research prototype made for android-5.0.0_r3.

There is also this research paper from 2017, titled “Privacy Threats through Ultrasonic Side Channels on Mobile Devices”. The authors of this paper found out for example that

• Advertising platforms such as Google’s Universal Analytics and Facebook’s Conversion Pixel provided services utilizing this technology. The researchers analyzed three commercial solutions: Shopkick, Lisnr and Silverpush.
• 234 Android applications analyzed by the researchers were constantly listening for ultrasonic beacons.
• Out of 35 stores visited in European cities, 4 were using ultrasonic beacons at the time of the research.

Anyway my interest is not just about blocking advertising trackers. Even though the marketing departments may be the largest consumer of this technology, it can be utilized in many other ways as well.

The Nearby Messages API is a publish-subscribe API that lets you pass small binary payloads between internet-connected Android and iOS devices. The devices don’t have to be on the same network, but they do have to be connected to the Internet.

Nearby uses a combination of Bluetooth, Bluetooth Low Energy, Wi-Fi and near-ultrasonic audio to communicate a unique-in-time pairing code between devices.

The concerns about the Nearby Messages API are:

1. Its ability to pass small binary payloads, i.e. presumably executable code.
2. That while it is easy to disable Bluetooth and WiFi on a smart phone, it is not so easy to disable the microphone.

Question:

Are there ways to block or at least detect the use of ultrasonic side channels or Google Nearby Messages API on my smartphone?

## Is there a scenario where a gnoll flesh gnawer can move at least 45 feet during its Rampage bonus action?

The base movement speed of a gnoll flesh gnawer is 30 feet, and if it activates rampage by bringing a creature to 0 hit points, it can move an additional 15 feet for a total of 45 feet during “normal” combat.

But is there a way that rampage could be triggered for the flesh gnawer after it gains a movement speed of 90 feet from its Sudden Rush action? This should allow the flesh gnawer to traverse 135 feet in one turn.

Ideally this would require only actions/abilities possessed by the various gnoll types, but I am open to other first-party/non-homebrew solutions for Dungeons and Dragons 5e that may make this possible.

Potentially relevant text from some of the gnoll actions are listed below:

Sudden Rush

Until the end of the turn, the gnoll’s speed increases by 60 feet and doesn’t provoke opportunity attacks.

Incite Rampage (Possessed by the Gnoll Pack Lord)

One creature the gnoll can see within 30 feet of it can use its reaction to make a melee attack if it can hear the gnoll and has the Rampage trait.

Rampage

When the gnoll reduces a creature to 0 hit points with a melee attack on its turn, the gnoll can take a bonus action to move up to half its speed and make a bite attack.