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.

198 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8
votes
1answer
306 views

Is there a strictly non-deterministic one-counter language whose complement is one-counter?

Let $A= \{L \mid L \;\text{is one-counter and \(\bar{L}\) is also one-counter} \}$ Clearly, $\text{Deterministic one-counter} \subseteq A$ Is it the case that $ A = \text{Deterministic one-counter}$...
7
votes
0answers
92 views

Automata that is Turing complete if you add a nondeterminism

Pushdown automata have an interesting property: non-deterministic ones belong to a different computational class than deterministic ones. This is in contrast to finite state and turing machines, for ...
7
votes
2answers
384 views

Automaton equivalent of the π calculus?

If Turing Machines are the automata equivalent of the $\lambda$ calculus, what is the automaton equivalent of the $\pi$ calculus? I suppose it would be some class of automata that resembled a Turing ...
6
votes
0answers
103 views

Where did our present regex notation originate?

First question, and my apologies if it is off-topic! This question suggests to me I may not be totally off-base. Where did our present regex notation originate? I am particularly wondering how <...
6
votes
0answers
267 views

Why does Non Determinism not enhance FA like it does for PDA

Both Deterministic and Non deterministic Finite Automata can recognize the same universe of regular languages. On the other hand, Deterministic Push Down Automata can only recognize a subset of ...
5
votes
0answers
276 views

Why does Turing Tumble need gear bits to be turing complete?

I understand intuitively that gear bits in the massively successful Turing Tumble game (funded by kickstarter) are necessary for Turing completeness*. I had a fantasy about building a computer with ...
5
votes
0answers
126 views

Reduction from clique to bag automata

I am trying to figure out a reduction to prove $W[1]$-hardness for this, but I am having significant trouble. Here is the problem: Bag Automaton: A non deterministic finite state automaton $M=(Q,I,s,...
4
votes
0answers
398 views

KMP Algorithm, Pratt's Minimisation/optimization of Knuth's original DFA based algorithm

The Original Knuth's Algorithm is based on DFA and it depends on the alphabet size. And Then, Pratt optimised it to be independent of Alphabet Size. But, All the ...
4
votes
0answers
161 views

How does Earley parsing using an automaton work?

As described in this paper, you can use an pre-computed automaton to speed up an Earley parse. I'm not interested in the rigorous proof of this, but just how the basic algorithm works so that I can ...
4
votes
0answers
104 views

Quality of Reduction of finite automata using different congruences

I am looking for an example, which corresponds to what I've learned in my Applied Automata Theory Class: Given a NFA $\mathcal{A}$, a $\approx _\mathcal{A}$ quotient automaton can be bigger then a $...
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. ...
3
votes
0answers
31 views

Are automata useful in software verification?

I contrast the paradigm of SMT-based verification of software, such as in LiquidHaskell with the approach based on automata. To me it appears that automata are only used in the paradigm of model ...
3
votes
0answers
37 views

What's the difference between a Generalized Nondeterministic Finite Automaton (GNFA) and a Generalized Transition Graph (GTG)?

I've recently come across a few articles that talk about a "Generalized Transition Graph" (GTG), but I've never heard of such a thing before. This other answer to a similar question leads me ...
3
votes
0answers
125 views

Algorithms to match regular expressions containing backreferences

I'm trying to come up with an implementation of a matcher for regular expressions containing backreferences like: ([a-c])x\1 which would match ...
3
votes
0answers
148 views

Do Combinational Logic circuits describe a set of languages?

I was looking at this picture: https://upload.wikimedia.org/wikipedia/commons/thumb/a/a2/Automata_theory.svg/640px-Automata_theory.svg.png Which made me think, that if all Turing Machines PDA's and ...
3
votes
0answers
53 views

How to apply insights from the theory of codes to alternating codes?

The book Theory of codes by J. Berstel and D. Perrin from 1985 studies variable-length codes. The focus is less on error-correction and compression, but more on algebraic properties, synchronization ...
3
votes
0answers
2k views

What are some applications of 2 stack pushdown automata?

What are some real world application for 2 stack pushdown automata, as i can only find pushdown automata applications in the internet
2
votes
0answers
39 views

Whether there exists a probabilistic automaton satisfying $\Pr \{ x \in L\}=\frac{\Pr \{ x \in L_1\}}{\Pr \{ x \in L_1\}+\Pr \{ x \in L_2\}}$

Suppose that there are two probabilistic automata $A_1$ and $A_2$ with a same finite alphabet $\Sigma$. The languages of them are $\mathcal{L}_{1} \subseteq \Sigma^*$ and $\mathcal{L}_{2} \subseteq \...
2
votes
1answer
65 views

this language and acceptance by queue automaton

I don't know how to prove or show that: $ L_1 = \{xx|x \in \Sigma^\ast\} $ (that can be accepted by queue automaton) If it would be possible, show by deterministic queue automaton, if not, by non-...
2
votes
1answer
23 views

Measuring the difficulty of a sequence-to-sequence problem using automata theory

Automata theory measures the difficulty of language recognition problems by using an automaton that can accept or reject for the given string. However, I want to measure the difficulty of a sequence-...
2
votes
3answers
52 views

PDA for a language where the second part is not the reverse of the first part

I came across an exercise for constructing a PDA for the following language: $$L = \{ncm \mid n,m\in\{a,b\}^* \text{ and } n \ne m^R\}.$$ Where $L \subseteq ({a,b,c})^*$ So $n$ and $m$ are both a ...
2
votes
0answers
45 views

can a DFA with only final states be minimized?

I need to construct a DFA for a certain language with as little states as possible. so far my "best" solution contains 15 states. however, people claim it is doable in 7 states only. I tried for ...
2
votes
0answers
82 views

Which of these languages is regular? The Pumping Lemma seems to show none are

I've been reviewing past paper questions for an automaton course, and came across a question which effectively asks, which of these languages is regular? $$ \{\ 0^m1^{(m \times n)}0^n\ \colon\ m,n\ge ...
2
votes
0answers
176 views

Does SLR(0), LALR(0) exists?

I read about LL(1), LR(0), SLR(1) and LALR(1) in many online sources and even in dragon book. However I found that no one talks about LL(0), SLR(0) and LALR(0). So I googled and come up against these ...
2
votes
0answers
103 views

Intersection of two deterministic parity automata

Given two deterministic parity automata $A_1=(Q_1,\Sigma,\delta,q_{01},c_1)$ and $A_2=(Q_2,\Sigma,\delta,q_{02},c_2)$ with the finite set of states $Q_i$, the finite alphabet $\Sigma_i$, the ...
2
votes
1answer
182 views

Brzozowki's algorithm doesn't work for this corner case

I'm a newbee learning DFA minimization. And I found that(strangely) Brzozowki's algorithm cannot give me a minimized DFA on this example: In this DFA, $S_0$ and $S_1$ are nondistinguishable and ...
2
votes
0answers
37 views

How to know a certain grammar is parse-able

Is it possible to parse all kinds of structured data and give them a semantic meaning? For example, C++ is a really complicated language and I could never imagine a parser would be possible for it. ...
2
votes
0answers
647 views

Understanding definitions of Deterministic Context Free Grammar and Deterministic Pushdown Automaata

I read following here: Unambiguous grammars do not always generate a DCFL. Example: For example, the language of even-length palindromes on the alphabet of 0 and 1 has the unambiguous context-...
2
votes
0answers
282 views

Powerset construction of minimal NFA will result into minimal DFA?

I was just thinking about the powerset construction and it is clear to me that the powerset construction will result into a DFA $D$ with possibly redundant states, as the NFA $N$ is not minimized. But ...
2
votes
0answers
61 views

How many states in a 2 delay (or n delay) transducer (using DFA)?

An n delay transducer in the context of the problem simply means that the output is same as the input but after waiting for 2 more symbols in the input. 2-delay transducer: We can't show any result ...
2
votes
0answers
270 views

Context free grammar as minimal solution of a system of equations

It is a well-known fact that language generated by a context-free grammar is the minimal solution of a particular system of equations, for example: $$\begin{align*} X &=\{{\epsilon}\} \cup Y\\ X ...
2
votes
0answers
78 views

Proof $\{u\colon |u| \text{ is odd and $b$ is in the middle}\}$ is not deterministic

Without using pumping lemma for deterministic context-free languages I need to prove that the language $\{u\colon |u| \text{ is odd and $b$ is in the middle}\}$ is not deterministic. Someone ...
2
votes
0answers
73 views

NPDA, guessing capability and stack as an exclusive resource

Context Free languages is exactly the class of languages recognized by Nondeterministic Push Down Automata (NPDA). We can view a nondeterministic transition as a guess; for example if $L = \{x x^R \}$...
2
votes
0answers
98 views

How does a minimal DFA ensure minimal computational cost?

I just went to read wikipedia to check a point on FA minimization, and I read there the following sentence: The minimal DFA ensures minimal computational cost for tasks such as pattern matching. ...
2
votes
0answers
114 views

When is the best time to include an ε-transitions in a NFA state diagram?

While doing my NFA homework in my automata class, I feel like I'm not taking advantage of the ε-transitions I'm learning about. I can solve problems without using it. It's not like I really need it, ...
2
votes
0answers
68 views

(Symbolic) Equivalence of deterministic infinite word transducers with restriction

Given a deterministic infinite word transducer (also called deterministic generalized sequential machine) with the following restriction: There is exactly one initial state All states are final The ...
2
votes
0answers
431 views

Example of execution fragment of multi-process transition system

Here is a simple transition system of beverage vending machine: The exemplary execution fragments can look like this: Now, imagine we have multi-process TS where processes are identical and ...
1
vote
1answer
24 views

Complement of equality problem of Turing machine is recognisable or not

Complement of equality problem of Turing machines is unrecognisable or not-recognizable but How?. As per my knowledge it is recognisable if you can decide its accept condition but not Reject and ...
1
vote
0answers
25 views

How to prove existance and construct finite-state transducer between two different FSM?

For example I have 2 simple FSM. I will use regular expression for clarity. ...
1
vote
0answers
12 views

What to do with operators with the same precedence in an unambiguous grammar?

I'm trying to create an unambiguous grammar for a calculator that uses $+$, $-$, $*$, $/$ and $()$. From watching videos and reading articles online, I understand how to create the grammar with $+$, $*...
1
vote
0answers
42 views

Different PDA design processes — both valid?

This video shows how to design PDA from a CFG: https://www.youtube.com/watch?v=ZImtQBMSW_Y Basically, we always have 4 basic states, and one of them is a "hub" for loops that implement ...
1
vote
1answer
44 views

Intuition for irregular languages

I'm struggling in understanding how to recognize irregular languages. I know what the meaning of irregular language but still find it hard to recognize. Are there any tips to recognize better and to ...
1
vote
1answer
122 views

Building non-deterministic automata

I'm trying to make non deterministic automata for specific language . I cant understand my mistake! Rules: 1){a,b,c} 2) if I have the sequence "bb" and later in the word I have the sequence &...
1
vote
0answers
22 views

Configuration of a space bounded turing machine

A configuration of a Turing machine is defined as the following: an ordered triple $(x, q, k) ∈ Σ^* × K × N$, where $x$ denotes the string on the tape, $q$ denotes the machine's current state, and $k$...
1
vote
3answers
323 views

Conversion of nfa with self-loop to one without self-loop

For every nondeterministic finite state automata that has self-loop(s), there exists an equivalent nfa that does not have any self-loop. How can we prove this statement in a general basis without the ...
1
vote
0answers
28 views

Name of this 2D automata

Today I had a weird dream about a kind of automata. Each automaton has a finite 2D grid wrapped around like a torus, formatted as a table. Execution starts in one cell. Each step it executes whatever ...
1
vote
1answer
86 views

Construct regular expression that contains the substring

I need to write a regular expression for the following set of strings on Σ = {a, b, c} in which the number of b’s is even, and contains abcba as a substring. So far, the even number of b's can be ...
1
vote
0answers
304 views

Queries regarding simulation of multi-tape turing machine using single tape turing machine

I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" by Jeffrey Ullman,John Hopcroft and Rajeev Motwani, where I came across the simulation of MULTI-TAPE ...
1
vote
0answers
62 views

A state space for river crossing puzzle

I am solving the river crossing puzzle with 6 participants. You must transfer all the people across the river in this flash game respecting the following rules: The ferry can carry no more than 2 ...
1
vote
1answer
187 views

Converting DFA to Regular Expression Using State Removal

I'm trying to convert the following NFA to a regular expression. I've attached my work below and end up with the expression $aa^*bb^*$. As far as I can tell, this doesn't seem correct but I've been ...