Questions tagged [automata]

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

Filter by
Sorted by
Tagged with
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 ...
Tips's user avatar
  • 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$ ...
Gaussianlover's user avatar
-4 votes
0 answers
30 views

DFA, Pumping Lemma and Regular language [closed]

For proving this question can I get some help? Thank you
Gaussianlover's user avatar
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, ...
Money Mit's user avatar
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, ...
Money Mit's user avatar
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,$...
Kantig Shoter's user avatar
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 ...
Sachihiro's user avatar
  • 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 | ...
Money Mit's user avatar
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 ...
Pedro Duarte's user avatar
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 ...
RV math's user avatar
  • 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 ...
boinka's user avatar
  • 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 ...
Mark Santolucito's user avatar
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 ...
NoCap's user avatar
  • 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 β€œπ‘π‘Žπ‘Žπ‘Žπ‘Žπ‘π‘Žπ‘π‘Žπ‘β€ ...
FunkyFlame's user avatar
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.
Achiya Ben Natan's user avatar
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 ...
M. Sperling's user avatar
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}...
NoCap's user avatar
  • 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 ...
MathCrackExchange's user avatar
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 ...
bestgamer14's user avatar
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]
adelorean's user avatar
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 ...
NitaStack's user avatar
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 ...
Jack Roserwod's user avatar
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 ...
MC From Scratch's user avatar
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 ...
Pagliaccious's user avatar
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 ...
Duong Tran's user avatar
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 ...
NitayStack's user avatar
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 (...
Shaun's user avatar
  • 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 ...
NitayStack's user avatar
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 ...
Vladyslav Chobotok's user avatar
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). ...
Camille's user avatar
  • 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 ...
Nixa's user avatar
  • 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 + ...
nothatcreative5's user avatar
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 ...
timtombobjohn's user avatar
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 #𝑏(𝑀) &...
Eric movchan's user avatar
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, ...
tchappy ha's user avatar
  • 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 ...
user1868607's user avatar
  • 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 ...
Suleyman Kiani's user avatar
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 ...
user1868607's user avatar
  • 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{...
Max Stuthmann's user avatar
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 ...
volairs22's user avatar
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 ...
Toxic Pusher123's user avatar
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$ ...
Jerry Ding's user avatar
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 "...
JobStack's user avatar
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 ...
Hari Seldon's user avatar
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 ...
RandomGuyOnMath's user avatar
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 ...
Rico1990's user avatar
  • 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 ...
Mr User's user avatar
-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{ ...
user3134725's user avatar
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
Chehak Malhotra's user avatar
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 ...
mark's user avatar
  • 97

1
2 3 4 5
…
37