# Questions tagged [automata]

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

1,820 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
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$ ...
30 views

### DFA, Pumping Lemma and Regular language [closed]

For proving this question can I get some help? Thank you
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, ...
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, ...
1 vote
46 views

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 ...
1 vote
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 ...
1 vote
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 ...
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 ...
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 ...
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 “𝑏𝑎𝑎𝑎𝑎𝑏𝑎𝑏𝑎𝑏” ...
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
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 ...
32 views

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
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). ...
1 vote