# Questions tagged [automata]

Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

1,849 questions
Filter by
Sorted by
Tagged with
32 views

### Getting from DFAs to regular expressions by solving a system [closed]

Given a deterministic finite automaton (DFA), there is a way to construct a regular expression that has the same language as the language of that automaton. There are several ways, but I'm insterested ...
20 views
+100

### How can we construct a NFA that accepts the substring matches

By "substring matches" (I'm not sure how to call it), I mean a binary string $x$ (something like 0011...) for a string $u$ in a regular language $L$ and a substring $w$ of interest, where ...
1 vote
19 views

### Is it decidable to check whether a regular language contains a word NOT of the form $uuv$? [closed]

Is the following problem decidable? Given a regular language $L \subseteq \Sigma^\ast$, check if $L \cap \{uuv \mid u \in \Sigma^+, v \in \Sigma^\ast\} \ne L$; i.e. whether there is a word in $L$ ...
• 11
37 views

### Construction of a Finite State Automaton given a grammar

I have been studying formal language and automata theory from Mathematical Methods in Linguistics (Partee et al.). Specifically, I have been learning about finite state automata, formal languages, and ...
66 views

• 10.6k
227 views

### What does it mean when the transition function of a NFA returns an empty set?

Given a NFA, $N = (Q, \Sigma, q_0, \partial, F_Q)$, where $\partial$ is the transition function $Q \times (\Sigma \cup \{ \varepsilon \} ) \to \mathcal{P}(Q)$. So $\partial(q, a)$ returns a set, ...
1 vote
81 views

### Role of Automata Theory in Today's Biology

Recently I have been studying some mathematical biology, in particular reading about central dogma of biology, how genes code for proteins. When reading about it, one of the things that fascinated me ...
26 views

### Problem understanding proof about deterministic pushdown automaton

So I already posted this in Computer Science Stack Exchange but haven't received any real answers and my exam is tomorrow, so I'll post it here too hoping for some clarification: I'm having problem ...
32 views

### Why doesn't the following idea prove the statement "If $A_{1}, A_{2}$ are regular languages then so is $A_{1}+A_{2}$"

Theorem Why doesn't the following idea prove the statement "If $A_{1}, A_{2}$ are regular languages then so is $A_{1}+A_{2}$"(concatenation operation) Argument If one designs the automaton ...
• 578
50 views

### Find the quotient of $L_1$ and $L_2$.

We want to find the quotient of languages $L_1$ and $L_2$. My question is what happens when the length of a word in $L_2$ is greater than the length of the word in $L_1$, for instance: $abc$ and $cc$. ...
• 63
1 vote
56 views

### Building a DFA/NFA to prove that a language is regular - exercise

I was given the following exercise and am having a hard time coming up with an intuition for it. Given a regular language $L$ on the alphabet $\Sigma$, prove that the following language is regular by ...
• 463
26 views

### If L is accepted by some deterministic PDA then L has the prefix property.

The question is from Ullaman and Hopcroft Automata theory book. A Language is said to have prefix property if for all words in L, no proper prefix of any of those words exist in L. Prove that if L is ...
31 views

### DFA automatic unit of two languages

Greeting, I have problems understanding the assignment in the field of automata theory and formal languages. The task says: Construct a minimal DFA that accepts the following languages: It is ...
50 views

21 views

### Proving that the language Lq = {x.y : x and y are binary strings and [x.y]2 ≤ q} is not regular if q is irrational

I have this assignment on finite automatas and tried to solve it but I have a question on the string s to use for the pumping lemma. I have the intuition that for q = square root of 2, I might want to ...
98 views

### Does pumping lemma ever fail? [closed]

Consider the language F = {$a^i$$b^j$$c^k$ | i, j, k ≥ 0 and if i = 1 then j = k}. Show that F is not regular. Show that F acts like a regular language in the pumping lemma. In other words, give a ...
1 vote
64 views

• 347
1 vote
47 views

### Number of automatas in single output automaton of n inputs

In John von Neumann's lecture titled Probabilistic Logics and the Synthesis of Reliable Organisms From Unreliable Components there is a defination 1 of single output automaton on page 3. And it is ...
196 views

### Is $M(L)=\left\{w \in L \mid \forall v \in \Sigma^+,vw \notin L\right\}$context-free?

$L$ is a context-free language. We define $M\left(L\right)=\left\{w \in L \mid \forall v \in \Sigma^+,vw \notin L\right\}$ . It seems like $M\left(L\right)$ is the set of strings in $L$ which are not ...
• 11
43 views

### Regular expression of a formal language with a number of a's equal to a multiple of 7 and a number of b's not equal to a multiple of 5?

$$L_{26} = \{w\ |\ |w|_a \equiv 0 \text{ (mod 7)} \wedge |w|_b \not\equiv 0 \text{ (mod 5)}, w \in \{a, b\}^*\}$$ The language is defined as above, how would one go ...
109 views

### What is Push Down Automata without null?

Q) Give a PDA without null for the language L = {x ∈ (0,1)* | n1(x)>n0(x)}. It is easy to create a PDA for this, but what does "without null" signify here?
• 11
1 vote
170 views

### Prove that minimal DFA is minimal

How to prove that a minimal DFA is actually minimal? The book I'm reading has the following proof, but there are parts I don't understand: ...to show that $\widehat{M}$ is minimal, is harder. Suppose ...
• 145
1 vote
103 views

### nondeterministic finite accepter's maximum walk length for string

For NFA(nondeterministic finite accepter), how long can a walk labeled string w be? For example, the following graph has 4 length from $q_1$ to $q_2$ for string $a$(...
• 145
1 vote
200 views

### DFA and regular expressions

I'm currently working on solving a question that requires determining which of the given regular expressions is equivalent to the language of the DFA provided. However, I'm encountering two primary ...
• 375
67 views

### CFG for $L = \{w_1w_2 \cdots w_{2n} \mid n > 0, w_i \in \{a, b\}, 1 \leq i \leq 2n, w_j = b, w_{n + j} = a \ \exists j, 1 \leq j \leq n\}$

I think this is somehow related to the language describing all strings not of the form $ww, w \in \{a, b\}^*$, but I am still not quite sure how. Of course, I have done some thinking and it is evident ...
1 vote
54 views

### Suppose we have unambiguous context-free language, how can we calculate the number of words that can be represented by $n$ terminals?

I am new to formal language theory, apology if this question seems obvious. Here are some definitions from formal language theory: Definition. Let $\mathcal{V}$ be a set of variables (usually denoted ...
• 1,711