# Questions tagged [automata]

Questions about mathematical devices that read an input stream symbol by symbol and use a state transition map to produce an output stream, maybe using secondary storage.

1,498 questions
Filter by
Sorted by
Tagged with
22 views

### Is it possible to create a NFA that accepts only n*“a” or n*“b” inputs?

I'd like to create a NFA that accepts only inputs like "aaaaa";"a";"bb";"bbb", but not like "aab";"aabaa". Is the even possible? As far as I ...
15 views

29 views

### Prove language is not Turing-recognizable using contradiction

Show that the language L = {<M>| M is a TM and does not accept <M>} is not Turing-recognizable. Note: Prove by contradiction. No need for reduction. This is the problem I am trying to ...
29 views

### DFA for language

I want to give a DFA for the language which contains the words X ∈ {0,1,2}* for which the number of 0's + number of 1's is even AND the number of 1's + the number of 2's is odd. I tried many ...
20 views

### Finding the language of a given CFG

I'm trying to find the language of the given CFG $S \to aB \mid bA \mid a \\ A \to bAA \mid aS \\ B \to aBB \mid bS$ I understand that the productions $S \to aB, S \to bA, A \to aS$ and $B \to bS$, ...
23 views

### Construct a PDA that recognizes $L = \{w : w \neq a^n b^n : n ≥ 0\}$

I'm trying to find the PDA of the above language. I understand that this is the complement of the language $L_1=\{w : w=a^nb^n : n\geq0\}$ However, I can't understand the idea behind constructing the ...
16 views

### Complement of equality problem of Turing machine is recognisable or not

Complement of equality problem of Turing machines is unrecognisable or not-recognizable but How?. As per my knowledge it is recognisable if you can decide its accept condition but not Reject and ...
12 views

### What would be an accepting sequence of configurations for this PDA?

What would be an accepting sequence of configurations for this PDA? I'm not sure how to approach this question, unless it's just trial and error?
38 views

### PDA for the language { $a^i b^j c^k \mid i,j,k \geq0, 7j = 5i + 6k$ }

I have seen this similar question but I can't seem to apply the same technique for the equation $7j = 5i + 6k$
22 views

### Proving undecidability of a language with mapping reductions

I'm referring to questions like this one: Mapping reduction to show NeverHalt is undecidable I understand with Turing reductions, you have to use oracle calls of the unknown language you're trying to ...
34 views

### $\omega$-automata where string is accepted iff a final state is accessible from starting state

I am wondering if $\omega$-automata with the following acceptance condition are valid. An input string is accepted iff one of the final states occurs at least once. This differs from Buchi automata in ...
51 views

### Proving that a language is a CFL

Assume that $L_1 \subseteq \Sigma^*$ is a CFL and that $y \in \Sigma^∗$ is a string. I need to prove that the language $L_2 = \{x \in L_1 \mid x \text{ does not contain$y$as substring}\}$ is a CFL. ...
26 views

### Proving Undecidability with reductions - Why do some proofs not use an Oracle?

I'm specifically referring to this group of questions here: https://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf So as I've learnt it, say we want to prove a new Language L is ...
23 views

### Convert the Finite Automata (FSA) into its equivalent regular expression, using stepwise minimization

I was doing an assignment of Theory of automata but while doing this question I am stuck there is no such state that can be eliminated even from transition table. I am very confused and stuck please ...
34 views

### Prove that the following language is not a regular language

Prove that the following language is not a regular language: $L = \{ 0^x1^y | x, y \geq 1\text{ and } x \geq y\vee (x < y \wedge y \mod x = 0)\}$ Is there anyone to prove this ?
20 views

### Extended NPDA implementation

In Formal grammars course we have a task to implement an extended NPDA (a pushdown automata where taking any amount of symbols from the stack is allowed (including ε) and it can be in several states ...
50 views

### Infinite prefix-closed context-free languages contain an infinite regular subset

The Problem: Say that a language is prefix-closed if all prefixes of every string in the language are also in the language. Let C be an infinite, prefix-closed, context-free language. Show that C ...
39 views

### $L^{\prime}=\{x \# y \mid x y \in L, y x \notin L\}$ where $L$ is regular

Hey I'm trying to prove that the following Language is regular so far couldn't find a way, hope someone can help me $L^{\prime}=\{x \# y \mid x y \in L, y x \notin L\}$ where $L$ is regular.
36 views

### An algorithm to check if two DFA are disjoint

What is the algorithm to check if two DFA are disjoint? I want to know if there exist any string accepted by both automata.
23 views

### Worst case of subset construction (NFA to DFA) [duplicate]

I am wondering what generic example there is so that an NFA with $n$ states results into a DFA with $2^n$ states after the conversion by the subset construction. I know there is the example by ...
100 views

### PDA and context-free languages

How can we prove that: Class of linear bounded PDA languages ∼ Class of CFLs I know that for a linear bounded PDA there is a constant $k$ such that the stack size for $w$ is at most $k|w|$. I also ...
23 views

### How to prove existance and construct finite-state transducer between two different FSM?

For example I have 2 simple FSM. I will use regular expression for clarity. ...
37 views

46 views

### How to remove epsilon production from this Context Free Grammar?

I want to remove the epsilon production from the following grammar: S → [ S ] | SS | ε
34 views

### Given two DFA's accepting the same language, does one have to refine the other?

I have a logical question that I can't quite crack: Given two automata accepting the same language $L$, does one have to refine the other? In other words, if $A_1$ and $A_2$ both accept $L$, with ...
39 views

### Different PDA design processes — both valid?

This video shows how to design PDA from a CFG: https://www.youtube.com/watch?v=ZImtQBMSW_Y Basically, we always have 4 basic states, and one of them is a "hub" for loops that implement ...
17 views

### Decidability of directed strongly connected graphs

Consider the problem of determining if a directed graph is strongly connected. How to phrase it as a language and prove that it's decidable. My Thoughts : To think of decidability given a graph I ...
21 views

### Regular expression of an FA

If we convert an NFA to a DFA, is the regular expression of the DFA the same as the NFA? I know the difference between an NFA and DFA and the algorithm to convert an NFA to DFA
57 views

### Convert NFA to DFA

Is there a unique DFA for every NFA or there are more than one DFA an NFA can be converted to? I've read the algorithm for converting NFA to DFA.
44 views

20 views

35 views

### Finite automaton whose alphabet is $\mathbb{N}$

Is it possible to have a finite automaton where $\Sigma = \mathbb{N}$? Why or why not? I think it is possible to have a set of all natural numbers, however I'm not sure why.
### Is $\{\varepsilon\}$ a conventional way to mark the empty language?
I am grading an exercise in Automata and Formal Languages and see many of the students use $\{\varepsilon\}$ as the empty language. At first I thought this was an error, and I have asked the lecturer ...