# 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,564 questions
Filter by
Sorted by
Tagged with
37 views

### How to design PDA for this language?

I'm having a hard time trying to build the PDA for this language: $$L=\{a^nb^m: n,m \geq 1 \land m=4n+2\}$$ I don't know how many $a's$ should I push into the stack when reading $a$, and how many $a's$...
51 views

### Design an NFA to recognize the given language. (Table and diagram) [closed]

Construct an NFA over {a, b} that accept strings having aa as substring. Construct an NFA over {0,1,} that contain 0110 or 1001. Construct an NFA over {a, b} that accept strings starting with a ending ...
203 views

### How it's possible decide CNF by having a turing machine that decide SAT?

Suppose we have a Turing machine $M$ as black box that decide $SAT$ problem. Now suppse we have a $CNF$ formula $\phi$ with $n$ variables. How it possible checking satisfiblity of $\phi$ and then ...
10 views

### Finding out the language generated by a context-free grammar

how can i find out the language that accepted by this cfg : S -> A B | B C A -> B A | x B -> C C | y C -> A D | x D -> y
53 views

### Is there a complexity measure on regular grammars connected to the descriptional complexity of the DFAs?

This question is directed at DFAs/NFAs and regular languages and regular grammars. Define the "descriptional complexity" of a language as the size complexity of the family of DFAs that ...
29 views

### How do right contexts work in context-sensitive L-Systems?

I am working on an implementation of context-sensitive 2-L systems as described in The Algorithmic Beauty of Plants by Aristid Lindenmayer, and am in need of clarification regarding context matching ...
52 views

31 views

### Why linear bounded automata emptiness and finiteness isn't decidable? [duplicate]

We know that linear bounded automata has tape size based on input size which is limited. Context-sensitive languages are accepted by LBA. My question is that if LBA has limited tape size why it's ...
40 views

### Difference between Counter-machine and stack machine

I read from this question that counter automata is a push down automata with only one symbol allowed on the stack (plus a fixed bottom symbol). My question is counter machine means counter coexist ...
11 views

### Construct Deterministic Accepter for binary string containing at any position

do you have any idea of designing a deterministic accepter where the set of all these binary strings contains at any position? The string is: 0100101 So, the accepted input could be: 0100101 or ...
12 views

### Need literature on First order logic definibility through Automata

Actually I am in search of some good literature on defining First order logic through Automata. It will be very helpful if someone can give me some links.
67 views

### My proof for equivalence of DFA and NFA

I came up with this proof for the following theorem: If $L$ is a language produced by an nfa, then there exists a dfa $M$ where $L(M) = L$. Is it correct? If it's not, what are the flaws of my proof,...
25 views

### Handling infinite loop in implementation Pushdown Automaton (PDA)

I've got a basic implementation of a Pushdown Automaton which recursively checks the rules of a grammar in CNF to find whether a given input string is accepted or not, and it can also count the number ...
51 views

### Efficient Turing machine to check that an unary multiplication is valid

I'm trying to find an efficient one-tape Turing machine that accepts inputs in the form R=A*B iff the equation is indeed true. All three numbers are written in ...
30 views

### How can I represent this description in set builder notation?

The language that accepts strings with the number of 0s being congruent with 1%3 and an even number of 1s over the alphabet {0, 1}.
23 views

### Correct complement of a regular language when the union of the languages do not lead to entire set of strings over the given alphabet?

I have a question that says that the complement of a regular language given as: $L_1=\{a^nb^m|(n+m)<5\}$ is $L_2=\{a^nb^m|(n+m)\geq5\}$ over $\Sigma=\{a,b\}$, and therefore, we can simply construct ...
30 views

### Designing a NFA that accept the set of strings that contain an even number of substrings 01

I'm new in theory of computation. Here {0,1} set of input symbols. I tried to make the NFA from L(M)= set of all accepted strings, but unable to complete it. Can someone give some hints that how ...
74 views

### Is the language "substrings of a regular language that are over half the length of the superstring" regular?

We say $x$ is a majority substring of $y$ if $y \in \Sigma^* x \Sigma^*$ and $|x| \geq \frac 12|y|$. If $B$ is a regular language, is the set of majority substrings of $B$ regular? I was provided the ...
28 views

### Counter automata with a bound on the counters?

It is widely known that emptiness of counter automata is undecidable since two counters are enough to simulate a Turing machine (see the classic book from Hopcroft and Ullman, for example). However, ...
4k views

### Would it be wrong to say that the processor (and hardware) is the implementation of an interpreter for machine language?

The question is basically in the title. I know that a computers hardware is of course some physical object, where as the interpreter is some abstract thing that does something abstract with the code ...
96 views

### What is the meaning of the pipe symbol here?

I am reading Distributed Algorithms by Nancy Lynch. In chapter 16, I came across the pipe symbol. Does this mean the same as "or" in some programming languages or could someone explain that ...
69 views

### Can a non deterministic finite automaton go into infinite loop?

Here is the exact same question but on deterministic finite automaton. The case for deterministic finite automaton is simple. For each state only one transition is possible for each input symbol and ...
62 views

### Regular language closed under homomorphism

I am trying to solve problems from the textbook 'Introduction to the Theory of Computation' by Micheal Sisper, 3rd edition. I am attempting to show various properties of regular languages and their ...
Let $S$ denote a deterministic process which generates a certain string, described through a Hidden Markov Model. More specifically, for a process with alphabet $\mathcal{A}$ and $n$ hidden states, ...