Questions tagged [automata]
Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques
1,820
questions
1
vote
1
answer
45
views
Is the Language $L = \{a^n b^m c^k d^q e^r \,|\, n, m, k, q, r \geq 0\}$ a Valid Regular Language?
I am inquiring about the nature of language L. It appears that L is not categorized as a regular language due to its unique characteristics, which involve the need to count occurrences of multiple ...
- 378
0
votes
0
answers
32
views
Union of Regular Language [closed]
If $R$ is a regular language. Why isn't $R \cup E$ regular? $E$ being the empty string $\varepsilon$.
So for example can't we simply make the starting state also an accepting state and call $R \cup E$ ...
-4
votes
0
answers
30
views
DFA, Pumping Lemma and Regular language [closed]
For proving this question can I get some help?
Thank you
0
votes
0
answers
33
views
Regular Expression for the set of all binary strings that are of even length with at most 2 zeros
I asked the converse just recently. But now trying to understand this version..
I'm working with case work and then I will take the union of all three cases where its strings with no zeros, 1 zero, ...
- 89
0
votes
1
answer
41
views
Regular Expression for the set of all binary strings that are of even length with at least 1 zero
Also followup question is the set of all binary strings that are of even length with at least two zeros.
But for both questions I'm thinking of building my regular expression with casework, no zeroes, ...
- 89
1
vote
1
answer
46
views
Let $L$ be a regular language. Prove that $L_1$, the language created by removing all characters in odd places in all words of $L$, is regular
Let $L$ be a regular language. Prove that $L_1$, the language created by removing all characters in odd places in all words of $L$, is regular.
Completely stuck on this one. I tried building DFA,NFA,$...
- 458
0
votes
1
answer
29
views
Dfa for a language {0,1} that has even length or it ends with a 0.
Accepted strings would be {"", 11, 100, 1010, 1111} And it would reject everything that is not even length or it ends with a 0.
I constructed two dfa, one that accepts all possible even ...
- 119
2
votes
2
answers
61
views
Prove that if M is regular then sandwiched M is regular as well
Hi I'm having some confusion with regular languages and DFAs.
Let's say we have some language M defined as $M = \{11, 1010\}$. Then let's define some $M[0]$ be defined formally as $\{x_10x_2...0x_n | ...
- 89
0
votes
0
answers
43
views
Describing grammar language / which language does this automaton recognize
I'm studying some questions about Automaton / Regular Expressions and I'm stuck in these questions.
Question 54
Which language does the automaton below recognize?
Automaton image
I tried trial and ...
- 11
1
vote
1
answer
35
views
Design a finite state machine that performs the serial addition of three arbitrary binary numbers
Design a finite state machine (by its transition diagram) that performs the serial addition of three arbitrary binary numbers.
For a finite state machine for two binary numbers I got it, but for 3 ...
- 59
1
vote
0
answers
41
views
Infinite Recursion as the Intuitive Foundation for the Halting Undecidability Proof
all, I was wondering if my intuitive understanding of why the halting problem is undecidable is actually correct?
TLDR: Halting problem is undecidable because it leads to infinite recursion and never ...
- 145
0
votes
0
answers
62
views
Why do we care if a power series has roots
I am reading up on Christol's theoreom and an important part is that k-uniform transducers (where k is somehow related to prime numbers) preserve the algebricity of a formal power series (taking the ...
0
votes
2
answers
33
views
Let $L \subseteq \{a,b \}^* $ be a rational language. Show that $K$ is rational.
Let $L \subseteq \{a,b \}^* $ be a rational language. $K$ the subset of words in $L$ that does not have has a factor $a^2$ and $b^3$. Show that $K$ is rational.
If $A$ is a DFA that accepts L. I ...
- 55
-1
votes
1
answer
127
views
Construct an NFA over alphabet {𝑎, 𝑏} that accepts all words with more a’s modulo 4 than b’s modulo 3.
Construct an NFA over alphabet {𝑎, 𝑏} that accepts all words with more a’s
modulo 4 than b’s modulo 3. For example, “𝑎𝑎𝑏” is accepted as it has two
a’s and one b. The word “𝑏𝑎𝑎𝑎𝑎𝑏𝑎𝑏𝑎𝑏” ...
0
votes
0
answers
26
views
I want to prove the pumping lemma for context-free languages but instead of using Chomsky's form using a new form.
I will be grateful for your help.
The new form is A-> V1.....Vt where t is between 2 and 5.
can you give me a direction for the proof or a proof for this problem?
thank you in advance.
1
vote
0
answers
26
views
Can substrings of a regular language always be recognized by an "isolated" path in some finite state automaton?
I believe I have found a proof of the question I originally asked (see crossed out paragraph), but I have realized that what I actually need to prove is somewhat stronger. What I am actually wondering ...
- 343
2
votes
1
answer
32
views
Let $H ≤ F_A$ be finitely generated and $g \in F_A$. Show that it is decidable if $xgx^{-1} \in H$ for some $x \in F_A$
By the generalized word theorem, we know that if we have $H ≤ F_A$ finitely generated and $g \in F_A$, then $g \in H$ iff $\overline{g}$ is accepted in $S_H$ (Stalling's Automata of H).
Then, $xgx^{-1}...
- 55
5
votes
4
answers
1k
views
Does the set of all programs form a group that acts on machine state (essentially, i.e. with a few exceptions)?
Since the only thing a computer can do is modify its machine state, and you can always change from one state into another state (there exists such a program) and so each program is invertible; and if ...
- 20.8k
2
votes
0
answers
71
views
Are $111^*$ and $11^*1$ equivalent?
I know it is a trivial question but are $111^*$ and $11^*1$ equivalent? (I think yes because I can have 11 in both at minimum but that seems odd to be true). I am trying to understand automata theory ...
- 21
2
votes
1
answer
38
views
Find the mistakes(pumping lemma proof). Can you help me?
There are pumping lemma proof. I have to find one mistake. Please help me [lemma proof][1]
- 21
1
vote
0
answers
33
views
Let 𝐿 be a regular language. Prove all minimal automata for the language are isomorphic
I have started to study formal languages, especially finite automata and regular languages and I encountered some difficulties, i.e. Is this true:
Automata will be called isomorphic if, by changing ...
- 95
0
votes
0
answers
33
views
Prove that if L is a recursive language, then its complement Ls is also recursive
Considering that a language $L$ is recursive iff there exist a Turing machine $T$ that accepts every string of the language $L$ and rejects all strings that don't match the alphabet of $L$.
In other ...
0
votes
0
answers
38
views
Creating "Zigzag" context-free grammar of $2$ languages with the same letters
Given are $2$ right-linear grammars, forming $L_1$ and $L_2$. The alphabet $T$ is the same for both languages, and $\epsilon$ (empty word) doesn't belong to any of the languages.
What is an example of ...
- 992
0
votes
0
answers
26
views
Simulating a Turing machine by multiple Turing machines with fewer states
Could you simulate a Turing machine by a sequence of Turing machines each with strictly fewer states than the simulated machine? By a sequence of Turing machines I mean this: the first machine is ...
0
votes
0
answers
30
views
What is the purpose a 1,0 or 0,1 loop at the end of the language DFA?
Here is a finite-state automata without output:
Language recognition automata without output
In finite-state machine with output, I understand that the 1,0 or 0,1 would give an output of 0 if input is ...
2
votes
0
answers
56
views
Prove that L = {$w∈${a,b,c}$^*$|w contains "abc"} is regular with Nerode theorem?
How to prove that $L = \{w \in \{a,b,c\}^* \mid w \text{ contains } abc \}$ is regular using the Nerode theorem?
Attempt
If I show that there are a finite number of equivalence classes for this ...
- 53
1
vote
1
answer
56
views
Recalling a theorem from vague memory: A monoid, in some sense, cannot "describe" the language (over one letter?) of words of prime length.
It has been over a decade (already!) since I studied a module on formal languages & automata during my undergraduate Mathematics degree. In considering a few things in combinatorial group theory (...
- 43.5k
0
votes
1
answer
50
views
Prove or disprove that L = {$a^nb^m$ | $m ≠ 3n + 5$} is a regular
How can I prove or disprove that $L = \lbrace a^nb^m$ | $m ≠ 3n + 5 \rbrace$ is a regular language?
Attempt
Assume $L$ is regular, then its complement $L^\complement$ is also regular.
$L^\complement ...
- 53
0
votes
1
answer
67
views
Is the algorithmic problem for regular languages decidable?
I have an algorithmic problem, where I need to build an algorithm and say if the problem is decidable. Here it is:
Regular languages $L_1$, $L_2$, and $L_3$ are given by finite automata. Is the ...
1
vote
0
answers
28
views
How to ensure that one pattern of the string must be after other pattern in the string in WS1S?
I need to define a formula, which will be true for strings meeting this pattern (10)*1* (zero or more occurrences of 10, followed by zero of more occurrences of 1).
...
- 11
1
vote
1
answer
38
views
How can I determine the language from a DFA?
I was given three DFAs to solve.
I understand the first one is a*. I think the second one would be b*(a+)*.
I cannot figure out what the third one would be, it seems like there are too many different ...
- 11
1
vote
1
answer
51
views
Prove equivalence of two regex using basic identities.
I'm trying to prove the following identity
$$
(x+y)^* = (x^*y)^*x^* = x^*(yx^*)^*
$$
Using the following 12 identities
$L + M = M + L$
$(L + M) + N = L + (M + N)$
$(LM)N = L(MN)$
$\emptyset + L = L + ...
- 333
0
votes
0
answers
37
views
Number of quantifier alternations in prenex form of a formula
I'm currently studying hyperlogics and in particular HyperLTL/CTL*.
In model checking algorithms for such logics the number of quantifier alternations appearing in a formula can play an important role ...
0
votes
0
answers
18
views
Pushdown automaton for 𝐿 = {𝑤 ∈ {𝑎, 𝑏}∗∣#𝑏(𝑤) ≠ 2 ⋅ #𝑎(𝑤)}
I have been trying to build pushdown automaton but no clue or idea on how to start.
I got the solution but I cannot get it,
Solution I received
What I was thinking is $2$ possible variations
#𝑏(𝑤) &...
1
vote
0
answers
84
views
Is Pumping lemma so useful? (Michael Sipser "Introduction to the Theory of Computation 3rd Edition")
I am reading "Introduction to the Theory of Computation 3rd Edition" by Michael Sipser.
Pumping lemma is the following proposition:
THEOREM 1.70
Pumping lemma If $A$ is a regular language, ...
- 8,410
0
votes
1
answer
26
views
Adapting the definition of non-deterministic tree automata.
The following definition is from Doner (1970)
A bottom-up tree automaton is a tuple $\mathcal{A} = \langle Q, \Sigma, \delta, q_0, F \rangle$ where
$Q$ is a finite set of states.
$\Sigma$ is an ...
- 5,655
0
votes
0
answers
38
views
Prove that the following problem is undecidable by a reduction from the halting problem:
Prove that the following problem is undecidable by a reduction from the halting problem:
“Does a given Turing Machine M accept any string of form a^2k for k ≥ 1?”
I'm having trouble understanding the ...
0
votes
1
answer
44
views
Formal language encoding WS2S and closed under complementation.
It is known that the relations encoded in WS1S are also represented by the words accepted by certain finite automata and thus can be represented as regular languages.
A similar connection holds ...
- 5,655
0
votes
1
answer
56
views
Deterministic finite automata that accepts words with even number of zeros OR even number of ones
Dear Math Stack Exchange users!
I want to create a deterministic finite automata with max. 5 states, that accepts the language :
$$A:=\{u\in\{0,1\}^*\mid |u|_0\textrm{ mod } 2 \equiv 0\lor|u|_1\textrm{...
1
vote
1
answer
52
views
Busy beaver on right-moving turing machine?
So, unless I'm being very silly, it seems completely obvious, that the maximum number of 1s a right moving TM can write is equal to "the number states it has" - 1.
It can't really store ...
- 25
0
votes
0
answers
130
views
Simulation DFA on turing machine
We will encode all element of M - Deterministic Finite Automata and w in unary numbers.
For example
We will encode all element of M and w in unary numbers.
Q = {q2, q5, q9}
The first element of Q is ...
0
votes
0
answers
44
views
Emulating any Markov Process of N states using a restricted Markov Process of more than N states
Let's define an unrestricted family of Markov Processes on $N$ states as the set of all possible Markov Processes using the states $1, 2, ... N$.
To clarify, if we let $A$ be the current state and $B$ ...
- 406
0
votes
1
answer
50
views
Build automata for words with both "bab" and "abb"
I have two finite automata, one for words containing "bab" and one for words with "abb."
I wish to build automata that represent the multiplication of both (words with both "...
- 3
0
votes
1
answer
872
views
The set of all strings of 0's and 1's not containing 101 as a substring
I'm working through a textbook on automata theory (Introduction to Automata Theory, Languages, and Computation) and I'm stuck on the Exercise 3.1.3:
Write regular expressions for the following ...
1
vote
1
answer
331
views
Using pumping lemma show that language $L = \{a^{n^2} | n≥ 0\}$ is not regular.
Using pumping lemma show that language $L = \{a^{n^2} | n≥ 0\}$ is not regular.
Is this approach correct?
Let's assume that $L$ is regular so then the pumping lemma applies.
Let $w = a^{n^2} ∈ L$.
We ...
1
vote
0
answers
125
views
Proof of sentence "A language L is context-free if and only if L is accepted by a pushdown automaton."
I have the proof below in my lecture. I would be very grateful if someone could explain the argumentation for the case $\alpha = BC$. Furthermore, I do not fully understand the subsequent arguments ...
- 295
0
votes
1
answer
791
views
A regex that matches strings containing an even number of 0’s or even number of 1’s
I need to write a regex that matches strings containing an even number of 0’s or even number of 1’s. (Alphabet Σ= 0,1)
I have already tried ...
- 9
-2
votes
1
answer
55
views
Determining whether a given language is regular
Suppose language $L = \{\,a^{i} b^{k} : k \text{ divides } i\,\}$.
Some strings in $L$ include …
$\,a^{0} b^{1} = b \in L\,$ since $1 \text{ divides } 0$
$\,a^{1} b^{1} = ab \in L\,$ since $1 \text{ ...
- 151
0
votes
1
answer
34
views
If any language accpeted by a finite automata is regular then why do we convert to a DFA every time we need to prove a language as regular? [closed]
Theory of computation question. since all the automatas we have studied are finite then why do we convert to DFAs while proving any theorems
0
votes
1
answer
33
views
Nondeterministic Finite Automata symbolism
I haven't taken any discrete maths, therefore im trying to understand the syntaxes here
$${\displaystyle \delta :Q\times (\Sigma )\rightarrow 2^Q \rightarrow{\mathcal {P}}(Q)}$$
So, cartesian product ...
- 97