# Questions tagged [automata]

Questions about mathematical devices that read an input stream symbol by symbol and use a state transition map to produce an output stream, maybe using secondary storage.

1,418 questions
Filter by
Sorted by
Tagged with
17 views

### How to get a piece of the Pie? Theoretical Plate Stacking Problem

This is just a theoretical problem that I found in the wild and want to know your solution. A stack of plates is made between you a cousin and a few others. Every (4 to 7) many random hours the plate ...
18 views

### DFA to accept a String containing even number of both A and B, but rejects empty String

I want to draw a DFA to accept a String containing even number of both A and B, but rejects the empty String(ε) I have already drawn the DFA which accepts the above language, without rejecting the ...
16 views

### Solve and create its pda

The set of strings in {0, 1}* whose logical OR is 1. For examples, logical OR of 11011 is 1 so it has to be in set. Create its CFG and convert into PDA
17 views

### Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular?

Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular? I do not think it is. I recently posted a question and from there I was thinking if this language is regular. If we assume on the contrary, then there ...
29 views

### Designing CFG that accepts words of the form $b^n a c^{n+1}$

I want to design a context-free grammar for the language $$L = \{ b^n a c^{n+1} \mid n>0 \}.$$ I came up with the following grammar, but it accepts strings with any number of $c$. Kindly help me ...
21 views

### Formal Languages and Automata theory test [closed]

Can someone help to solve these two tests?? First version
23 views

### What are the practical examples of Semidecidable problems? Is NP problem a semidecidable problem?

I am going through a Turing machine topic. I know about decidable, semi decidable, and decidable problems. But honestly speaking, I did not get any practical examples of Semidecidable problems. Can ...
30 views

### Machine that recognizes more than countable languages - is it superturing (doing hypercomputation)?

I am reading thesis http://dspace.lu.lv/dspace/bitstream/handle/7/48857/298-71916-Dimitrijevs_Maksims_md09032.pdf?sequence=1 which says: Abstract Turing machines can recognize countably many ...
54 views

### A language that is not context free

I working through some textbook exercises, and came across a problem that I'm struggling with. Give a CFL $L$ such that $\{x|\forall y \in \Sigma^* \space xy \in L\}$ is not a CFL. I've got the idea ...
40 views

65 views

### what is the function of a turing machine

The main question asked me to build a certain turing machine such that given a word w over {0,1}* the turing machine accepts all such words and ends in accept state with the tape string = the word ...
75 views

### Computational power of a Turing Machine with infinite states

Consider a turing machine with infinite states. This machine is identical to a regular machine. Only that number of states could be infinite. Does this machine has more computational power than a ...
160 views

### Show $L =$ { w $\in (a,b) ^*$| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$ is regular

I try to show that this language is regular: $L =$ { w $\in \ (a,b) ^ *$| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$ If I build a NFA and run on it every substring of w (skip other letters ...
474 views

### Does P = NP in Cellular Automata of Hyperbolic Spaces?

I read a few years ago in this book that NP problems are tractable in the space of cellular automata in the hyperbolic plane. What does this mean? Does P = NP ...
60 views

### Proof that $\{0|1\}^*0\{0|1\}^n$ requires at least $2^{n+1}$ states

How can you prove that any DFA accepting the language generated by the regular expression $\{0|1\}^*0\{0|1\}^n$ requires at least $2^{n+1}$ states? I first attempted induction on $n$. But I don't ...
I am trying to understand this example of converting PDA to CFG but I am not getting the idea quite right. I do have the general understanding of theorem that if $p,q\ \epsilon\ Q$ and \$X \varepsilon\...