Generate code from automata

I am trying to figure out the process of generating code (set of instructions, implementation language specifics dont matter at this time) from an automata.

The description of my intent is vague because although I am an electrical engineer, with extensive coding experience, I have no theoretical CS background and I am struggling to even articulate what I mean. The issue at hand is related to a digital circuit that I am working with. At this point I am not even aware of what I need to start looking into. Another way of describing my intent is, say I got a transition model of a process with the data requirements that are associated with the states. Knowing that, can I generate a program that will implement that model? Is there a field of study that deals with problems like this? Or should I just develop some logic to solve a limited interpretation of the model?

I believe I am using incorrect or misleading terms from a CS standpoint but I will appreciate if I can get some guidance on how to formulate my intent and then try to understand the possible solutions, if any.

Thanks!

Need help with previous “Automata / Theory Of Computation” exam question

I passed by this question in a previous exam while studying for the “Automata / Theory Of Computation” and I am struggling to find answer. I would appreciate it if someone can help me with it:

This is the question:

a)On the basis of what was covered in class, draw the Venn diagram representing the following sets:

1.REXP: the set of the language given by all regular expressions

2.DFSA: the set of all languages recognized by deterministic FSAs

3.NFSA: the set of all languages recognized by non-deterministic FSAs

4.CFG: the set of all languages generated by context free grammars

5.PDA: the set of all languages recognized by PDAs

Can a Non-Deterministic Pushdown Automata recognize $ \# a^nb^{2^n} \# $ which a TM can?

$ \# a^nb^{2^n} \# $

such that

• The alphabet of the machine is {, a, b, x}.

• The symbol x will never appear on the input a.

• The contents of the tape at completion may be anything.

• The head begins on the lefthand #.

• n ≥ 0.

I know that a Turing machine could recognize this language. But can a NPDA recognize this language too? I am thinking it can but I do not know how to start proving how/why?

Are endmarkers necessary for Deterministic Pushdown Automata?

In the book by Kozen (Automata and Computability), the transition function of deterministic pushdown automata (DPDAs) is supposed, in contrast with non-deterministic pushdown automata (NPDAs), to accept as arguments triples $ (q, \sigma, \gamma)$ with $ \gamma$ that might be a right endmarker symbol. It is written: “The right endmarker delimits the input string and is a necessary addition. With NPDAs, we could guess where the end of the input string was, but with DPDAs we have no such luxury.” (p. 176). Can we show that this condition is necessary? Can we give an example of a language accepted by this kind of DPDA’s that is not accepted by any DPDA whose transition function has no argument with an endmarker?

Pushdown Automata for number of a less than 2 times number of b

Suppose we want to design a pushdown automata for $ L=\{x \in \{a,b \}^{*}:|x|_a<2|x|_b \}$ , can anyone check whether my automata works?

we have 4 states $ \{q_0,q_1,q_2,q_3 \}$ , three stack symbols $ \{S,A,B \}$ , start state $ q_0$ , accept state $ q_3$ , we have rules as following: $ q_0$ accepts nothing and push $ S$ onto stack to $ q_1$

$ q_1$ reads $ a$ and pops $ B$ , remain in $ q_1$

$ q_1$ reads $ a$ and pushes $ A$ , remain in $ q_1$

$ q_1$ reads $ b$ and pushes $ BB$ , remain in $ q_1$

$ q_1$ reads $ b$ and pops$ AA$ , remain in $ q_1$

$ q_1$ reads $ b$ and pops$ A$ and pushes $ B$ , remain in $ q_1$

$ q_1$ reads nothing and pops $ B$ , go to $ q_2$

$ q_2$ reads nothing and pops $ B$ , remain in $ q_2$

$ q_2$ reads nothing and pops $ S$ , go to $ p_3$

Backwards and forwards automata languages compared with regular languages

enter image description here

Is every language accepted by a BAFDA regular? I am not even sure what the answer is. I tried thinking around canonical examples of non-regular languages (like $ 0^n1^n$ or $ \{ww | w \in \{0,1\}^{*}\}$ provable by Myhill-Nerode or by the Pumping Lemma) but cannot think of a suitable BAFDA for any of them.

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.