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.

Filter by
Sorted by
Tagged with
2
votes
3answers
3k views

NFA for binary words that do not end in 10

Construct an NFA over $\{0, 1\}$ whose language contains only words that do not end with $10$. This is one of the first problems in the book, so it's supposedly easy. I just can't figure it out. It's ...
2
votes
2answers
3k views

Pumping Lemma for regular language for $a^n$ where $n$ is even fails

$$L=\{a^n \mid \text{\(n\) is even}\}$$ This is regular but fails in the pumping Lemma. Assuming $m=4$, $w=aaaaaa$, $|w|=6$ (even). Let $w=xyz$, $x=a$, $y=aaa$. We have $|y|>0$ and $|xy| \le m$. ...
24
votes
4answers
79k views

How to show that a “reversed” regular language is regular

I'm stuck on the following question: "Regular languages are precisely those accepted by finite automata. Given this fact, show that if the language $L$ is accepted by some finite automaton, then $L^{...
1
vote
2answers
2k views

When generating a PDA from a CFG do I have a receiving state?

Thw Wikipedia article on Pushdown automata doesn't explain what the receiving state is for the generated PDA it just states that there is but one state.
6
votes
2answers
9k views

Cost in time of constructing and running an NFA vs DFA for a given regex

Repost from Stack Overflow: I'm going through past exams and keep coming across questions that I can't find an answer for in textbooks or on google, so any help would be much appreciated. The ...
5
votes
1answer
442 views

Is the set of minimal DFA decidable?

Let $\mathrm{MIN}_{\mathrm{DFA}}$ collection of all the codings of DFAs such that they are minimal regarding their states number. I mean if $\langle A \rangle \in \mathrm{MIN}_{\mathrm{DFA}}$ then for ...
4
votes
1answer
382 views

How to implement simulation on two LTSs?

Does any one know how to implement the simulation relation on two labelled transition systems (LTS)? I know how to do it for branching bi-simulation. The signature refinement theorem is used for ...
0
votes
1answer
643 views

Does this regular expression equal this automata?

I just came across an exercise which is to find a regular expression for the following automata, such that the regular expression and the automata generate the same language. One solution presents ...
49
votes
2answers
37k views

Is a push-down automaton with two stacks equivalent to a turing machine?

In this answer it is mentioned A regular language can be recognized by a finite automaton. A context-free language requires a stack, and a context sensitive language requires two stacks (which is ...
2
votes
1answer
783 views

LTS of this simple FSP

I have this finite-state process with the corresponding labeled transition system: The FSP is: ...
5
votes
1answer
537 views

Building a finite state transducer

I know it's possible to build a Finite State Transducer for converting numbers from base 2 to base 4 or 8 or other powers of 2 (translating from base N to base N^M is easy). However I've never seen a ...
5
votes
3answers
384 views

Is the set of codes of Deterministic Finite-State Automata a regular language?

Let $\Sigma$ be a given alphabet. Is there a way to code up Deterministic Finite state Automata (DFA) over $\Sigma$ as strings of $\Sigma$ in such a way that the corresponding subset of $\Sigma^*$ is ...
10
votes
1answer
157 views

Is this language Context-Free? [duplicate]

Possible Duplicate: Is this language Context-Free? The language is defined by $$(a+b)^*-\{(a^nb^n)^n\mid n \geq1 \}$$ is Context-Free Language? I believe that the answer is that it is not a CFL'...
30
votes
4answers
5k views

How to simulate backreferences, lookaheads, and lookbehinds in finite state automata?

I created a simple regular expression lexer and parser to take a regular expression and generate its parse tree. Creating a non-deterministic finite state automaton from this parse tree is relatively ...
3
votes
1answer
324 views

Time to construct a GNBA for LTL formula

I have a problem with the proof for constructing a GNBA (generalized nondeterministic Büchi automaton) for a LTL formula: Theorem: For any LTL formula $\varphi$ there exists a GNBA $G_{\varphi}$ ...
0
votes
2answers
3k views

Are supersets of non-regular languages also non-regular?

I have to proof that if $L_1 \subset L_2$ and $L_1$ is not regular then $L_2$ it not regular. This is my proof. Is it valid? Since $L_1$ is not regular, there does not exists a finite automata $M_1$ ...
2
votes
1answer
1k views

Eliminating useless productions resulting from PDA to CFG converison

In my class we used a Pushdown Automata to Context Free Grammar conversion algorithm that produces a lot extraneous states. For example, for two transitions, I am getting the following productions ...
10
votes
1answer
781 views

How to prove that ε-loops are not necessary in PDAs?

In the context of our investigation of heap automata, I would like to prove that a particular variant can not accept non-context-sensitive languages. As we have no equivalent grammar model, I need a ...
2
votes
1answer
1k views

Automata that recognizes Kleene closure of permutations of three symbols

This is an automata theory homework question. I need to create DFA that meets the following criteria: Alphabet $\Sigma = \{ a, b, c \}$ Machine accepts empty string and strings of length that is a ...
10
votes
2answers
528 views

Optimal myopic maze solver

I was fooling around with Google Blocky's Maze demo, and remembered the old rule that if you want to solve a maze, just keep your left hand to the wall. This works for any simple-connected maze and ...
4
votes
1answer
977 views

Transforming an NFA into an NFA of similar size but without $\epsilon$-transitions

I'm learning for the exam and have problems with this task: Describe an algorithm that transforms a given NFA $A = (Q, \Sigma, \delta, q_0, F)$ (which may have $\epsilon$-transitions) into an ...
23
votes
1answer
3k views

Decide whether a context-free languages can be accepted by a deterministic pushdown automaton

Given a context-free grammar G, there exists a Nondeterministic Pushdown Automaton N that accepts exactly the language G accepts. (and visa versa) There may also exist a Deterministic Pushdown ...
7
votes
1answer
10k views

Relation between simple and regular grammars

I am reading "An Introduction to Formal Languages and Automata" written by Peter Linz and after reading the first five chapters I face below problem with simple and regular (especially right linear) ...
4
votes
2answers
353 views

DFA with limited states

Lets $L_z \ := \{ a^i b^i c^i : 0 \leq i < z \}$ $\{a,b,c\} \in \sum^*$ there is a DFA with $\frac{z(z+1)}{2}+1$ states - How can I prove this? And I need largest possible number $n_z$, for ...
15
votes
5answers
2k views

Are there undecidable properties of non-turing-complete automata?

Are there undecidable properties of linear bounded automata (avoiding the empty set language trick)? What about for a deterministic finite automaton? (put aside intractability). I would like to get ...
9
votes
4answers
2k views

Words that have the same right- and left-associative product

I have started to study non deterministic automata using the book of Hopcroft and Ullman. I'm stuck in a problem that I found very interesting: Give a non deterministic finite automaton accepting ...
7
votes
1answer
341 views

What is a good reference to learn about state transition systems?

I am studying different approaches for the definition of computation with continuous dynamical systems. I have been trying to find a nice introduction to the theory of "State transition systems" but ...
51
votes
8answers
96k views

How to prove a language is regular?

There are many methods to prove that a language is not regular, but what do I need to do to prove that some language is regular? For instance, if I am given that $L$ is regular, how can I prove that ...
4
votes
1answer
144 views

Power of nondeterministic type-1 min-heap automaton with both a heap and a stack

I have asked a series of questions concerning capabilities of a certain class of exotic automata which I have called min-heap automata; the original question, and links to others, can be found here. ...
5
votes
2answers
189 views

Computational power of nondeterministic type-1 min-heap automata with multiple heaps

I have asked a series of questions concerning capabilities of a certain class of exotic automata which I have called min-heap automata; the original question, and links to others, can be found here. ...
4
votes
0answers
103 views

Computational power of nondeterministic type-2 min-heap automata

I have asked a series of questions concerning capabilities of a certain class of exotic automata which I have called min-heap automata; the original question, and links to others, can be found here. ...
4
votes
1answer
4k views

How does a two-way pushdown automaton work?

Note that by "two-way pushdown automaton", I mean a pushdown automaton that can move its reading head both ways on the input tape. I recently had the question of determining the computational power ...
5
votes
6answers
21k views

Are Turing machines more powerful than pushdown automata?

I've came up with a result while reading some automata books, that Turing machines appear to be more powerful than pushdown automata. Since the tape of a Turing machine can always be made to behave ...
5
votes
4answers
5k views

A DFA for recognizing comments

The following DFA is a lexical analyzer which is supposed to recognize comments. The lexical analyzer will ignore the comment and goes back to the state one. I'm told that there's something wrong with ...
15
votes
1answer
2k views

Computational power of deterministic versus nondeterministic min-heap automata

This is a follow-up question of this one. In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: ...
8
votes
1answer
613 views

Proving closure under complementation of languages accepted by min-heap automata

This is a follow-up question of this one. In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: ...
16
votes
1answer
559 views

Proving closure under reversal of languages accepted by min-heap automata

This is a follow-up question of this one. In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: ...
19
votes
3answers
388 views

Is this language defined using twin primes regular?

Let $\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}.$ Is $L$ regular? This question looked suspicious at the first glance and I've realized that it is connected with the ...
16
votes
2answers
514 views

Languages accepted by modified versions of finite automata

A deterministic finite automaton (DFA) is a state machine model capable of accepting all and only regular languages. DFAs can be (and usually are) defined in such a way that each state must provide ...
23
votes
2answers
1k views

Is there a “natural” undecidable language?

Is there any "natural" language which is undecidable? by "natural" I mean a language defined directly by properties of strings, and not via machines and their equivalent. In other words, if the ...
25
votes
3answers
2k views

What are the conditions for a NFA for its equivalent DFA to be maximal in size?

We know that DFAs are equivalent to NFAs in expressiveness power; there is also a known algorithm for converting NFAs to DFAs (unfortunately I do now know the inventor of that algorithm), which in ...
44
votes
2answers
1k views

Determining capabilities of a min-heap (or other exotic) state machines

See the end of this post for some clarification on the definition(s) of min-heap automata. One can imagine using a variety of data structures for storing information for use by state machines. For ...
39
votes
2answers
6k views

Are there inherently ambiguous and deterministic context-free languages?

Let us call a context-free language deterministic if and only if it can be accepted by a deterministic push-down automaton, and nondeterministic otherwise. Let us call a context-free language ...
32
votes
2answers
1k views

Equivalence of Büchi automata and linear $\mu$-calculus

It's a known fact that every LTL formula can be expressed by a Büchi $\omega$-automaton. But, apparently, Büchi automata are a more powerful, expressive model. I've heard somewhere that Büchi automata ...
34
votes
9answers
4k views

What is the significance of context-sensitive (Type 1) languages?

Seeing that in the Chomsky Hierarchy Type 3 languages can be recognised by a state machine with no external memory (i.e., a finite automaton), Type 2 by a state machine with a single stack (i.e. a ...
10
votes
1answer
801 views

Algorithm to translate a deterministic Büchi automaton to LTL (when possible)

Linear temporal logic and deterministic Büchi automata are incomparable: DBA cannot express $FGa$, and LTL cannot express "at least each odd letter is 'a'". But sometimes it is interesting to know ...
7
votes
1answer
752 views

Converting a context free grammar to a PDA — is my solution correct?

I'm reviewing for my midterm and wanted to post this to see if anyone can spot any errors. Im supposed to make a PDA that recognizes this CFG: $\qquad\begin{align} S &\to R1R1R1 \\ R &\to ...
5
votes
1answer
401 views

Decidability of Machines

I cannot understand decidability really well. I have been reading from books and internet, but I am little bit confused. According to the book (as I understood), we can decide on decidability of a ...

1
26 27 28 29
30