# Questions tagged [automata]

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

1,965 questions
Filter by
Sorted by
Tagged with
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 ...
• 654
66 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
38 views

17 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 ...
• 1
65 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

• 83
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 ...
• 13
1 vote
112 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$ ...
51 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 ...
• 2,029
95 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 ...
43 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 ...
• 2,029
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 ...
23 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. ...
• 2,029
62 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
38 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 ...
• 37
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). ...
69 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 ...
• 2,029
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-...
• 43
73 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!
• 39
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 ...
• 43
1 vote
89 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, ...
• 331
110 views

### Proving that a NFA where all states must be on an accepting state is equivalent to a DFA

Here is the full question: Recall that NFA accepts a string as long as at least one of the states that the machine is an accepting state, after consuming the entire input. Here, we define strict-NFA ...
• 37
15 views

### is N-Σ-automaton a Non-Deterministic Finite Automata

I am trying to understand a part of this book Automata,Languages and Machines. K=N case I cant undesrtand the Topic because i dont get what a N-Σ-automaton, i tried to find something, but i only get ...
30 views

### ∈-closed & ∈-closure in NFA-∈

I came across this question in my automata theory class which is as follows Let NFA-∈, M=(Q, ∑, δ, q0 , F). A set S ⊆ Q is called ∈-closed if ∈-closure(S)=S. a) Show that the union of two ∈-closed ...
1 vote
I was trying to find the CFG for the language below. However, I couldn't do that. Can anyone help with this problem? $$\{1^n 0^m 1^k 0^p | n \geq 2, m,k,p \geq 1, n+k = m+p\}$$