# Questions tagged [finite-automata]

Questions about finite automata, an elementary automaton model with finite memory. It is equivalent to regular languages and the basis for many more complex models.

1,448 questions
Filter by
Sorted by
Tagged with
25 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 ...
26 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 ...
33 views

### What is the connection between finite automata and logic (sequential calculus)?

Languages recognized by finite automata are exactly those definable by sentences of the sequential calculus, and also exactly those definable by rational expressions (also called regular expressions) ...
19 views

### Finite Automaton to Turing Machine Example

I cannot seem to find an example of an NFA and Turing Machine that both accept the same languages. I am trying to understand how to convert an NFA to its equivalent Turing Machine and I think a simple ...
42 views

### Can $A_{TM}$ be mapping reduced to an unrecognizable language?

$A_{TM}$ is the language of pairs of ⟨M,w⟩ such that M is a TM that accepts w Can the language $A_{TM}$ be mapping reduced to an unrecognizable language? In other words, $A_{TM} \leq_m L$, and L is ...
33 views

### Regular expression for binary representation of even numbers?

I need help writing the regular expression over the alphabet (0,1) represent the even numbers in base ten. So basically the regular expression would show represent an even number in binary. (also if ...
53 views

### Existence of a CFL $L$ such that $\sqrt{L}$ is not CFL

Does there exist a CFL L such that the language defined as $L' = \sqrt{L} = \{w | ww \in L\}$ is not CFL? I feel that there is no such $L$ but obviously, I am unable to prove it. I am sorry but I have ...
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 ...
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 ...
40 views

### Proof regular languages are closed under homeomorphism

Let $\Sigma_1 , \Sigma_2$ be alphabets. Let $L\subseteq \Sigma_1^*$ be a regular language, and let $h:\Sigma_1^* \rightarrow \Sigma_2^*$ be a homomorphism. Proof $h(L)$ is regular. I have written a ...
18 views

### Is language decideable (subset)?

I'm working on a proof for following question $L=\{(R,S)\mid \text{R,S are regular expressions and } L(R)\subset L(S)\}$. Show that this language is/isn't decidable. A language is decidable iff we ...
18 views

### $\{<M>: M \text{ is a finite automata and L(M) contains a word of form } a^ib^j\}$ is decidable?

How can we show that the language $K = \{<M>: M \text{ is a finite automata and L(M) contains a word of form } a^ib^j\}$ is decidable?
18 views

### Is my proof for the regularity of the language $A/B$ correct?

This problem is from Sipser's Theory of Computation 3rd Edition. 1.35 Prove that $A/B = \{\omega \ | \ \omega x \in A \ \mathrm{for\ some \ } x\in B\}$ is regular where $A$ is regular and $B$ is any ...
37 views

### Prove by contradiction that the language with unequal number of a's and b's is not regular

Consider the language $$L = \{w \mid w \text{ has an unequal number of a’s and b’s}\}$$ where Σ = {a, b}. Prove that L is not regular. Hint: Try proof by contradiction. Would this be the right Answer: ...
37 views

### A state machine that is either DFA or NFA: is it possible?

I am studying Crafting Interpreters, and although I understand the responsibility of the Scanner (or Lexer), I still cannot understand if it is a deterministic finite automaton or non-deterministic ...
14 views

### DFA from Regular Expression [closed]

QUESTION: Draw an equivalent DFA that accepts the following language RE= (a*+b*)*.
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.
16 views

### NFA -> DFA powerset construction worst case [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 Hopcroft ...
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.
15 views

### Grammar for $\{ (n_a(w) - n_b(w)) mod\ 3 = 2 \}$

What is the grammar for $$\{ (n_a(w) - n_b(w)) mod\ 3 = 2 \}$$ please guide me with this. I tried to draw DFA to find grammar but I can't. any help is much appreciated.
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 ...
29 views

### FA for when length of $w$ is $4$ or $w$ contains the substring $01$

I have been trying to create an FA for the language. $\{w \in \{0, 1\}^∗ , |w|= 4 \vee w \text{ contains the substring }01\}$ I created one that accepts words that contain the substring $01$, but I ...
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. ...
42 views

### Why is the Turing machine rather than the finite automaton the main model for computation if computers have finite memory?

Any physical computational device clearly has finite memory. On the other hand the input can be external and could therefore potentially be infinite. This idea is perfectly captured by the ...
110 views

### Is the language of DFAs that accept at some string in $\{b, c\}^*$ decidable?

Let the language $K = \{\langle W \rangle: W \text{ is a DFA on } \{a, b, c\} \text{ and } L(W) \text{ contains some string in } \{b, c\}^*\}$. Is $K$ decidable? Is it sufficient to define $M$ as ...
37 views

### Can converting NFA to DFA change the language?

In the context of studying the conversion from an NFA to the equivalent DFA, I came across the following NFA, which accepts all strings over the alphabet $\{0,1\}$ which contain $01$: After I ...
155 views

### Minimal number of states for an NFA of all different words

Given $\Sigma =\{0,1,@\}$, I am looking at a language $L=\{u@v | u,v\in \{0,1\}^k\wedge u\neq v\}$. So $u,v$ have only $0,1$s, same length $k$, yet are different. Also, for me $k$ is a known constant. ...
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 ...