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.

Pushdown Automata – can you have multiple transition functions options between 2 states?

I was wondering if you have 2 states, lets say q0 and q1. Are you allowed to have multiple options to transition between these 2 states?

For example,

 - if you have a 1 and the stack is empty, push it on the stack, and transition to q1  - if you have a 0 and the stack is empty, push it on the stack, and transition to q1  - if you have a 1 and there is a 1 on the stack, push it on the stack, and transition to q1  - if you have a 1 and there is a 0 on the stack, pop the 0 off, and transition to q1  - if you have a 0 and there is a 0 or 1 on the stack, push it on the stack and stay in q0 

I was wondering if this is allowed, and it knows what to do given the scenario?

Sorry if this is obvious, I have been looking at some PDAs and haven’t seen any that have multiple options to transition between states and was wondering if it was allowed.

There is a difference between malware detection using automata and family behavior graph?

I have a question,

There is a difference between dynamic malware detection using automata and family behavior – graph?

I think that they are both relying on API function calls but I don’t understand if there is any major difference between them.

Please help me,

if you’re not sure what I’m talking about:

automata – https://www.researchgate.net/publication/309710040_Detecting_Malicious_Behaviors_of_Software_through_Analysis_of_API_Sequence_k-grams

family behavior – graph – https://drive.google.com/open?id=1dOZ80FcaBiDHRDW4kusdxXGZw2C9aXfK

of course, they are free

first one – just click on Request full-text and it will download the pdf files. the second one is google drive link.

Thank you.

Minimizing automata with reverse and det

So, by the Bzozowski theorem, if A is DFA det(rev(det(rev(A))) would have minimal number of states. And for the most of them work. But for this example, I can’t figure out why it doesn’t. I have an DFA which is NOT minimal (the min. automata have 2 states ) but det(rev(A)) is the same automata (obviously det(rev(det(rev(A))) is also the same). Can you tell me what am I doing wrong ? Tnx.

enter image description here

Create automata from non regular grammar

I have two grammars:

 L → ε | aLcLc  L → ε | aLcLc | LL  

This two grammars are equals but the first one is regular, so it produces a regular language and a Finite State Automata. Instead, the second one is non regular but it might produces a regular language.
To prove it, I want to create two differentes automata: the first one should be a correct automata and if the second one can’t be create then the language is not regular. Are all this statments correct?
If so, can someone help me build these two automata? Thank you!

A deterministic finite state automata for finding all (potentially overlapping) regular expression matches?

I was working on a bioinformatics practice problem named Finding a Protein Motif on rosalind.info. In essence, I was given a particular regular expression N[^P](S|T)[^P] and is asked to find all matches.

Solving that problem is not the goal here, I have a ‘working’ solution here. In essence, I manually designed a state machine that can find all matches for that regular expression.

And here is a ‘visualization’ of the state machine, to make it clear how it is manually designed.

digraph G {     0 [label="0,''"]     1 [label="1,'N'"]     2 [label="2,'NN'"]     3 [label="3,'NS|NX'"]     4 [label="4,'NNS'"]     5 [label="5,'NSS|NXS'"]     0 -> 1 [label="N"]     0 -> 0 [label="P"]     0 -> 0 [label="S"]     0 -> 0 [label="X"]     1 -> 2 [label="N"]     1 -> 0 [label="P"]     1 -> 3 [label="S"]     1 -> 3 [label="X"]     2 -> 2 [label="N"]     2 -> 0 [label="P"]     2 -> 4 [label="S"]     2 -> 3 [label="X"]     3 -> 1 [label="N"]     3 -> 0 [label="P"]     3 -> 5 [label="S"]     3 -> 0 [label="X"]     4 -> 1 [label="N(accept)"]     4 -> 0 [label="P"]     4 -> 5 [label="S(accept)"]     4 -> 0 [label="X(accept)"]     5 -> 1 [label="N(accept)"]     5 -> 0 [label="P"]     5 -> 0 [label="S(accept)"]     5 -> 0 [label="X(accept)"] } 

The classical theory allows us to convert a regular expression to a non-deterministic finite-state automaton and then convert it to a deterministic finite-state automaton through subset construction. In particular, subset construction guarantees that if there exists an accepting computation, then the deterministic finite-state automaton would also accept.

Let say I have a regular expression that matched twice, the corresponding deterministic finite-state automaton would accept after the first match, but then it doesn’t know what to do in order to set it to the right state for detecting overlapping matches. I guess I could start one character after the beginning of the first match, which in the worst case would probably lead to quadratic time, as we could imagine with {.*} on {{{{{}

In the worst case, I expect quadratic time (e.g. {{{{{}}}}}}), but it would be great if the timing is output-sensitive, for I believe a good deal of cases aren’t quadratic in output size.

It would be great if my state machine used to find all matches can be generalized (apparently sometimes it need linear space, not just a single state) or automatically designed. Do we know if there are existing theories for that?

How to detect infinite loop exist in linear bounded automata (LBA)?

The following theorem from Michael Sipser’s book “Introduction to the Theory of Computation” states:

$ A_{\textrm{LBA}}= \{ \langle M, w \rangle \mid \text{$ M$ is an LBA that accepts string $ w$ } \}$ .

THEOREM: $ A_{\mathrm{LBA}}$ is decidable.

On the proof part, it states:

The idea for detecting when $ M$ is looping is that as $ M$ computes on $ w$ , it goes from configuration to configuration. If $ M$ ever repeats a configuration, it would go on to repeat this configuration over and over again and thus be in a loop.

I do not understand this: “If $ M$ ever repeats a configuration, it would go on to repeat this configuration over and over again”. What if $ M$ only repeat one configuration, then halts?