Questions tagged [automata]

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

Filter by
Sorted by
Tagged with
-1 votes
0 answers
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 ...
user avatar
  • 654
0 votes
0 answers
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
user avatar
-1 votes
0 answers
38 views

How do I prove $\leq_{T}$ is a symmetric relationship on $P(\Sigma^*)$

Does a reflexive and transitive Turing reducible relation on the powerset of all strings imply symmetry, too? Here is my understanding. If $\leq_{T}$ is transitive on $P(\Sigma^{*})$, then given $A \...
user avatar
0 votes
0 answers
46 views

What is the purpose of a witness in existential projection?

I am reading my class notes and have come across the following terms - The existential projection of a language $B \subseteq \Sigma^{*}$ is the language, $\exists B \subseteq \Sigma^*$ defined by $\...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 1
0 votes
1 answer
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 ...
user avatar
3 votes
2 answers
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
0 votes
0 answers
26 views

Creation of nondeterministic finite-state machine for a word which doesn't contain a certain symbol

The given alphabet is $$\Sigma = \left\{ a, b, c \right\}$$ I am looking for a nondeterministic finite-state machine which accepts the following words: $$L=\left\{w\in \Sigma^* \mid \exists x\in\Sigma:...
user avatar
0 votes
1 answer
38 views

Automata - Prefix

Assume we have $L=\{ab\}$, then is it correct to say that $\mathbb{prefix}(L)=\{\epsilon,a,b,ab\}$ ? I mean - is epsilon included in every prefix? If I have $L=\{a^*a\}$, then in this case $\mathbb{...
user avatar
  • 654
2 votes
1 answer
72 views

$L_1$ and $L_2$ are regular and we have a new language $\text{pref}(L_1,L_2) = \{x \in \Sigma^* \mid \exists u \in L_2\text{ s.t. }xu\in L_1\}$

prove that $\operatorname{pref}(L_1,L_2) = \{x \in \Sigma^* \mid \exists u \in L_2 \text{ such that $xu\in L_1$}\}$ is regular. So I was thinking proving this question by building an automata for ...
user avatar
  • 55
0 votes
1 answer
38 views

Prove that $L=\{a^n b^l : n \leq l\}$ is not regular by pumping lemma

I'm currently trying to prove that $L=\{a^n b^l : n \leq l\}$ is not regular by pumping lemma My proof: If we choose $w$ such that $w=a^P b^P$, then since $|xy| \leq p$, $y$ must be $a^P$, meaning it ...
user avatar
  • 111
1 vote
1 answer
27 views

Can NFAs have infinitely many edges?

This question is about whether the definition of weighted Non-deterministic Finite state Automata (NFAs) excludes the possibility of infinitely many transitions. The definition of Finite State ...
user avatar
0 votes
1 answer
46 views

creating regular expressions from given language

The first question is $L_1 = \{w \in \{a,b,c\}^∗ \mid \text{$w$ ends with $ca$}\}$ I started by creating a DFA for that for better understanding and then making a regular expression. and the regular ...
user avatar
1 vote
0 answers
34 views

Quantifier elimination for non-polynomial functions

I lack much of the theoretical background for QE (my background is primarily optimization and control), but have stumbled across it in the process of learning about hybrid automata & decidability. ...
user avatar
  • 48
0 votes
0 answers
24 views

How can I prove that $L´=\{uv|u,v\in\sum^*,vu\in L\}$ is regular if $L$ is regular? [duplicate]

For language $L$ over alphabet $\sum$ define language $L´$ as follows: $L´=\{uv|u,v\in\sum^*,vu\in L\}$ Is then $L´$ also regular? I think that yes, because if we can take $u$ and $v$ as we want, we ...
user avatar
1 vote
1 answer
21 views

Is the language represented by the set of binomials following some rule regular?

Consider a $\Sigma = \{\binom{0}{0},\binom{1}{0},\binom{1}{1},\binom{0}{1}\}$ and a language $L$ over $\Sigma$ such that strings in the language have the "bottom row" of the string as the ...
user avatar
  • 1,713
0 votes
1 answer
39 views

Finding the equivalent regex for a formal grammar

We have the following formal grammar: $a, b$ are terminal symbols. $S, A, B$ are non-terminal symbols. $S$ is the startsymbol. Thinking in terms of a nondeterministic finite automata $q0$ indicates ...
user avatar
1 vote
0 answers
43 views

Looking for the IBM report: Beckman, Categorical notions and duality in automata theory

I am desperately looking for an old IBM research report, cited at the end of Chapter 3 in Samuel Eilenberg's book Automata, Languages and Machines (1974): Beckman, Categorical notions and duality in ...
user avatar
  • 36.1k
1 vote
2 answers
122 views

Prove that the shift operation on regular languages preserves regularity

I have the following question: I have seen the statement that for the Shift operation, defined as: Shift($L$) = { $yx$ | $xy \in L$} Where the following is mentioned: "For any regular language $L$...
user avatar
1 vote
1 answer
18 views

Looking for the name of a special type of automata.

I am trying to find the name of the automaton with a beautiful property. No matter which state that you start from, there is a same sequence of $k$ transitions so that you end up reaching at the same ...
user avatar
  • 149
0 votes
0 answers
32 views

Proof of Pumping Lemma: Why can we set the pumping constant to the number of states?

I'm learning the proof of the Pumping Lemma for regular languages. The proof is carried out using an arbitrary string having length of at least the number of states in the DFA. As such: The language ...
user avatar
  • 1
2 votes
2 answers
48 views

Prove or disprove that $(L_1\cap L_2)L_3 = L_1L_3\cap L_2L_3,$ where $L_i$ denotes a formal language

Prove or disprove that $$(L_1\cap L_2)L_3 = L_1L_3\cap L_2L_3,$$ where $L_i$ denotes a formal language Proof: $$\begin{align} (L_1\cap L_2)L_3 &= \{xy \mid (x \in L_1 \land x\in L_2 ) \land y\in ...
user avatar
  • 83
1 vote
2 answers
36 views

Constructing grammar for $a^ib^j$ / $i\neq j$

I want to construct a grammar for the following regular expression: $a^ib^j / i \neq j$. I did it the following way: $S_1 \rightarrow aaSb | aaAb$ $A \rightarrow aA | \epsilon$ $S_2 \rightarrow aSbb | ...
user avatar
2 votes
0 answers
24 views

constructing grammar for 1*0*1(1+0)*

I want to construct a grammar for the following regular expression: $1^*0^*1(1+0)^*$. I did it the following way: $S \rightarrow AB1C$ $A \rightarrow 1A | \epsilon$ $B \rightarrow 0B | \epsilon$ $C \...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 13
1 vote
1 answer
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$ ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 2,029
0 votes
3 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 3
0 votes
0 answers
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 2,029
1 vote
1 answer
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$ ...
user avatar
0 votes
1 answer
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 ...
user avatar
0 votes
1 answer
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. ...
user avatar
  • 2,029
0 votes
2 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 37
0 votes
1 answer
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). ...
user avatar
3 votes
2 answers
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 ...
user avatar
  • 2,029
0 votes
1 answer
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-...
user avatar
  • 43
0 votes
0 answers
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!
user avatar
  • 39
-1 votes
1 answer
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 ...
user avatar
  • 43
1 vote
1 answer
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, ...
user avatar
  • 331
0 votes
1 answer
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 ...
user avatar
  • 37
0 votes
0 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
1 vote
0 answers
51 views

What does "stabilize" mean in Conway's game of life?

In wikipedia's article about Conway's game of Life, it often talks about a pattern eventually stabilizing, there's even a page about a type of seed called Methuselah which is "defined" as a ...
user avatar
4 votes
1 answer
121 views

Finding Context Free Grammar for a language

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\}$$
user avatar

1
2 3 4 5
40