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.

Constructing a directed graph for O(1) queries

I need help to design a data structure for a directed graph with the following properties:

  1. Initialization should be done in O(1) time.
  2. AddVertex(id1,id2,…idK) – Add a new vertex to the graph. The new vertex is added with id=N+1 where N is the number of existing vertices. id1…idK are the neighbors of the new vertex, such that there is an outgoing edge from the new added vertex to each of the vertices id1 .. idK. This should be done in O(1) time.
  3. GetNumberOfNeighbors(id) – Return the number of outgoing edges for a vertex with a given id (id is in 1..N). This should be done in O(1) time. All O(1) times are for worse case.

Thanks allot

Constructing elliptic curves defined over $\mathbb{Q}$ with fixed complex multiplication

I have the following problem: we know that for a field $ \kappa$ of characteristic $ 0$ usually an elliptic curve $ E$ defined over $ \kappa$ is such that $ End(E)\cong \mathbb{Z}$ . This means that one cannot hope to find an elliptic curve with complex multiplication choosing it “randomly”.

Suppose that i want to produce and elliptic curve over $ \mathbb{Q}$ whose $ End(E)$ is and order in $ \mathbb{Q}(\sqrt{-D})$ : what are the methods currently known to do it? Is it possible to write explicitly the isogeny corresponding to $ \sqrt{-D}$ ? (If it is in $ End(E)$ and $ D$ is not so large).

Thank you for your time.

Constructing a 3D virtual map from 2D Depth Maps and $x, y, z, \theta$ coordinates

Context: I intend on building a quadrotor which can generate a 3D virtual map of an area of which it captures photos with a 2D camera.

I plan on first training a Convulational NN to return a depth map from a 2D image, then use the information from that depth map along with the x, y, z coordinates and angular displacement of the quadrotor to generate this 3D map.

What do I need to learn in order to do something on this scale?

Any ways to make this easier?

Thanks, -ShreyJ

Nitro strength why some of the other constructing

Nitro strength don't work. • another factor that you are going to have to care for is the eating regimen. If you do not follow a proper weight loss plan, there is no Muscle building procedures in an effort to work for you. As a result, spend some time and to find the high-quality weight loss program with a view to help you during nitro strength muscle constructing process. • An primary part of all the Muscle constructing techniques…

Nitro strength why some of the other constructing

Constructing a model of $\mathrm{DCF}_0$ via forcing

As is mentioned in the introduction of this paper of Spodzieja there is a lack of ‘natural’ examples of differentially closed fields. The immediate naive guesses, namely the field of germs of meromorphic functions at some point, only partially work in that these structures contain differentially closed fields as substructures by Seidenberg’s embedding theorem but are not differentially closed themselves.

It seems that the while the sheaf of meromorphic functions is fairly rich, it’s always possible to find differential equations that are badly behaving at a given point. As someone who has been in the same room as people talking about set theoretic forcing, this made me wonder whether or not a ‘direct’ construction of a differentially closed field could be achieved with forcing. Essentially I want to take the field of germs of meromorphic functions at a generic point.

Does there exist a forcing extension $ V[G]$ such that for some $ z\in\mathbb{C}^{V[G]}\setminus \mathbb{C}^V$ the field of germs at $ z$ of meromorphic functions in $ V$ is differentially closed?

Of course this is equivalent to considering the ring of germs of holomorphic functions in $ V$ at $ z$ , since no such function can have a zero or pole at $ z$ . A potentially more general question could be asked in terms of direct limits along directed sets of open subsets of $ \mathbb{C}$ , but I wanted to focus on this simpler form first.

Super fancy list constructing in Python

Out of curiosity I was discovering the potential of the Ellipsis object in Python (...), and I discovered it doesn’t do a whole lot except for a handful of minor features. In an effort to make it useful, I decided to create the most fancy-pants constructor for a list that I could.

The function, super_list, takes an arbitrary number of arguments to be added to the list. Here are the features:

  • super_list(multiple, arguments, provided) -> Generates a list using the arguments provided. If an argument doesn’t follow any of the special features below, it is just appended to the array at the proper nesting level. This example returns [multiple, arguments, provided], a list of the arguments.

  • super_list(5, ..., 9) -> Takes advantage of the Ellipsis object to create something that looks like “x to y”, or a range. This particular example would produce a list containing [5,6,7,8,9], the number between 5 and 9.

  • super_list(arg, array.move_up, higher_arg, array.move_down, lower_arg) -> Sets the nesting level inside the list. Including array.move_up or array.move_down moves up or down one level of nesting in the list. This example produces [arg, [higher_arg], lower_arg], moving up and down the array chain with array.move_up and array.move_down.

One last big example:

super_list("first level", 5, ..., 9, array.move_up, array.move_up, "second level", 10, ..., 15, array.move_down, "down one level") 

produces

['first level', 5, 6, 7, 8, 9, [['second level', 10, 11, 12, 13, 14, 15], 'down one level']] 

So this is my current implementation:

def get_in_list(lst, indexes):   """Gets an item in a nested list by a list of indexes."""   return functools.reduce(operator.getitem, indexes, lst)  def super_list(*args):   """Special initialization syntax for lists."""   curr_index = []   result = []   for index, item in enumerate(args): # Iterate over args with indexes     el_type = type(...) # Type of the Ellipsis object     if isinstance(item, el_type): # Case: Ellipsis range generator       if index == 0:         get_in_list(result, curr_index).append(item)       else:         get_in_list(result, curr_index).extend(list(range(args[index-1]+1, args[index+1])))     elif item == array.move_up: # Case: move up one level in list       get_in_list(result, curr_index).append([])       curr_index.append(len(get_in_list(result, curr_index))-1)     elif item == array.move_down: # Case: move down one level in list       try:          curr_index.pop()       except IndexError: # Silently catch if user tries to move down too far in the list         pass     else: # Case: No special syntax - regularly append item to list       get_in_list(result, curr_index).append(item)   return result 

get_in_list is a function used to get an item at a list of indexes. This means that a[0][1] == get_in_list(a, [0, 1]).

My questions:

  • Is it too messy?

  • Is anything too long and could be implemented in a shorter way?

  • Is the program too confusing, and do you think it could be more verbose?

And obviously, any other comments you may want to add are appreciated. Thanks in advance!

Confused about constructing the “failure table” in Knuth-Morris-Pratt algorithm

I’m trying to learn how the “failure table” is constructed in the Knuth-Morris-Pratt algorithm since it seemed nontrivial to me that you could do it in $ O(k)$ time (where $ k$ is the length of the pattern, $ W$ ). To be clear, we let the failure table $ T$ be a length $ k$ array where $ T[i]$ is the length of the longest proper prefix of $ W$ which is also a suffix of $ W[1]\cdots W[i]$ .

I was trying to understand it better by reading the following code:

    vector<int> T(pattern.size());     T[0] = 0;     int j;     for (int i = 1; i < pattern.size(); i++) {         j = T[i - 1];         // Find largest j s.t. T[:j+1] == T[i-j:i+1]         while (j > 0 && pattern[j] != pattern[i]) {             j = T[j - 1];         }         T[i] = (pattern[j] == pattern[i]) ? j + 1 : j;     }     return T; 

The part I’m confused about is why pattern[j] == pattern[i] is enough to guarantee that $ T[i] = j + 1$ . I was trying to prove this inductively but have had no luck. I’ve phrased the problem as follows:

Suppose $ W[1]\cdots W[T[i – 1]] = W[i – T[i – 1]]\cdots W[i – 1]$ . If $ W[i] == W[j]$ , then is it true that $ W[1]\cdots W[j] == W[i – j + 1]\cdots W[i]$ ?

I can’t make any headway with this, nor can I see why it should be true. It still seems like we have to check $ W[\ell] = W[i – j + \ell]$ for all $ \ell = 1…j$ . I can’t figure out how to use the inductive hypothesis to prove this result. Do I have to use strong induction (where we assume all prior steps are true and not just the previous step) to prove this?