# Questions tagged [automata]

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

1,968 questions
Filter by
Sorted by
Tagged with
30 views

### Design a DFA for the language $L = \{a^n b \mid n \geq 0 \}$

Problem : Design a deterministic finite automaton for the language $L= \{a^nb \mid n \geq 0 \}$
1 vote
118 views

### Is it possible for an NFA to have only one state? [closed]

Is it possible for an Nondeterministic Finite Automaton (NFA) to have only one state? Wouldn't it make it deterministic (DFA)?
3 views

### Low boundary on number of equivalence classes $L_{reg}$ [closed]

In attempt to find a good way to detect how many equivalence classes there are for an alphabet $\Sigma$ under a languge L ( Two words are equvialent if there is no distinguishing extension between ...
22 views

### Automata Regular Expression that remembers n iterations

Given is $L = \{\sigma_1 ~u~\sigma_2~v~\sigma_3 ~|~ \sigma_{1,2,3} \in \Sigma,~~ u,v\in \Sigma^*,~ |u|=|v|,~ \sigma_2=\sigma_3 ~or~ \sigma_2=\sigma_3 ~~\mathbb{but ~~ not ~~ both} \}$ I do not ...
68 views

### How can I prove that L = {w ∈ {a, b, c, d} ∗ | #a(w) = #b(w) = #c(w) = #d(w)} is not context-free without using the pumping lemma?

I am stuck on this problem, I can prove it using the pumping lemma, but I'm wondering if I can also prove it using closure properties
40 views

19 views

### Is this a PDA for balanced parentheses language?

I have got following PDA: $A=(\{p, q\},\{0, 1\},\{Z\},\delta , p, Z)$ $\delta ( p, 0, Z) = \{(p, ZZ)\}$ $\delta ( p, 1, Z) = \{(p, \lambda)\}$ $\delta ( p, \lambda, Z) = \{(q, \lambda)\}$ Assuming ...
67 views

### On the general relationship between automata, expressions, and grammars

When I took Theory of Computation, the main points of interest were three kinds of automata: finite, pushdown, and Turing, one type of expression: regular expressions which are equivalent to finite ...
63 views

### What does it mean for a language to be sparse?

A language $A \subseteq \sum^{*}$ is sparse, and we write $A \in SPARSE$, if there is a polynomial q such that, for all $n \in N$, $$\left|A \cap \sum^{n}\right|\leq q(n)$$ The definition of a ...
39 views

### What is a prefix set?

I am trying to understand the following definition of prefix set - "A prefix set is a language $A \subseteq \Sigma^*$" such that no element of A is a prefix of any other element of A. I came ...
1 vote
29 views

### Find NFA for the language $L_1$ of all # that can be replaced by string of size 3 that would be in language $L$

Let $L$ be a regular language, and let $$L_1 = \{u_1\#u_2\# \dotsm \#u_n \mid ∃v_1,v_2,…,v_{n-1} \in \Sigma^3 \text{ such that } u_1v_1u_2 \dotsm v_{n-1}u_n \in L \}$$ where $\# \notin \Sigma$. For ...
26 views

1 vote
36 views

1 vote
48 views

### How can I generate the DFA with following condition

Give DFA's accepting the following languages over the alphabet$\{0,1\}$,The set of all strings such that each block of five consecutive symbols contains at least two 00s. This question is from ...
1 vote
116 views

### a^m b^n c^n prove it's not regular/pumping lemma

How to prove that $L = \{a^mb^nc^n \mid n, m \geq 0\}$ is not regular by the pumping lemma My attempt: Let's suppose $L$ is regular. There exists a pumping constant p, and we choose $w = a^pb^pc^p$ ...
54 views

### The number of states in DFA that accepts strings with length that is divisible by $3$ or $5$.

I know that the answer is $15$ states, but I cannot get my mind to understand why is that? which property makes it impossible to do it in less states? I've tried to mess with it for a long time and ...
96 views

### $a^nb^n$ language vs $a^nb^m$

I always read that $\{a^nb^n \mid n>0\}$ is not a regular language because automata doesn't have memory, while $\{a^nb^m \mid n, m>0\}$ is regular because we don't have to remember anything ...
1 vote
29 views

### DFA conversion through state elimination and arden's method

I have tried to convert the following DFA to regular expressions through two different methods: Arden's method, and state elimination one. I have arrived to two different regular expressions: Arden's ...
44 views

### What is the transition function of the given NFA?

I have a question regarding the following NFA: When I provide the formal definition, I am stuck at the alphabet $\Sigma$ and $\delta$ parts. Since the alphabet is not given, and no transitions are ...
12 views

### Pumping Lemma-prove a language is not regular

The question is to prove that the Language below is not regular, and I have used the pumping lemma technique I wanted to know if this is the correct solution so the CFG for it is let the grammer be ...
43 views

### Building a DFA from another DFA.

Let the language that the DFA accepts have a different definition. A word is in the language if and only if when we finish reading it we reach an accepting state AND atleast one time passed through ...
1 vote
39 views

### Induction on automaton [closed]

Let an automaton defined by the following transition table: 0 1 $\rightarrow$A A B $\leftarrow$B B A I have this finite automaton, and it recognizes the languages with only an odd number of $1s$ ...
37 views

### intersection of two regular expressions [closed]

If we have two regular expressions $L_1 = aba^*b^*c^*$ and $L_2 = a^*b^*c^*ab$, how do we get $L_1 \cap L_2$ get? I found the answer to be $L_1 \cap L_2 = ab + abab$ But I don't know how it was ...
24 views

### Solution Verification: Prove or Disprove: If $L$ is an irregular language and $F$ is finite language, then $F\cap L^+$ is regular.

Prove or Disprove: If $L$ is an irregular language and $F$ is finite language, then $F\cap L^+$ is regular. Note: $L^+=\bigcup_{i=1}^{\infty}L^i$. I will be attempting to prove this statement. ...
66 views

### DFA or NFA that accepts all words over the alphabet (a,b) that begins with ab and do not end with aa

Design a (deterministic or nondeterministic) finite automaton A such that L(A) consists of all strings over the alphabet {a, b} that begin with ab and do not end with aa. I have this question that is ...
1 vote
42 views

### Regular expression rules for union and concatenation with $\epsilon$ and $\emptyset$

I have four rules here that are true and I wanted to make sure I have a general intuition as of why. These aren't meant to be rigorous proofs, but rather simple explanations. Suppose $R$ is a regular ...
36 views

### What type of Automata can accept just Theorems of Propositional Calculus

As per title: What is the weakest type of automata that is capable of accepting just the theorems (deducible from any specific set of axioms) of Propositional Calculus (i.e. truth functional logic). ...
71 views

### Solution Verification: There exists an infinite set of different irregular languages such that their union is a regular language.

Prove or disprove: There exists an infinite set of different irregular languages such that their union is a regular language. My intuition led me to try to disprove, since if I had a set that is ...
36 views

### How can this all-NFA be converted to an DFA

an all-NFA was defined in Sipse as such: A (Q, Σ, δ, q0, F) that accepts x ∈ Σ∗ if every possible state that M could reach after reading input x is in F, so not at least one. If any branch in an all-...
80 views

### How to design a Mealy machine which is divisible by 3 or by 2.

How do I design a Mealy machine which outputs 1 if the binary number is divisible by 3 or by 2 considering the LSB is coming first? Appreciate the help!
42 views

### Worst case (highest) number of states for a DFA and NFA [closed]

I just started to learn about Automata and I came across a problem I could not wrap my head around. We let both A_1 and B_1 be regular languages defined by DFAs A and B. Let nA and nB be the number of ...
1 vote
90 views

### A mathematically brief analogue of M. Sipser's "Introduction to the Theory of Computation"

I am interested in a quite compact and mathematically rigorous textbook (or textbooks) on the theory of computation. I wish to cover the following three basic topics: automata theory, computability, ...