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
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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)
...
0
votes
0answers
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 ...
-2
votes
0answers
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 ...
-2
votes
1answer
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 ...
3
votes
1answer
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
-2
votes
1answer
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?
0
votes
0answers
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 ...
-1
votes
2answers
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:
...
0
votes
2answers
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 ...
-6
votes
0answers
14 views
DFA from Regular Expression [closed]
QUESTION: Draw an equivalent DFA that accepts the following language
RE= (a*+b*)*.
0
votes
1answer
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.
0
votes
0answers
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 ...
1
vote
1answer
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.
-1
votes
1answer
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.
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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.
...
1
vote
1answer
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 ...
-1
votes
1answer
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 ...
1
vote
1answer
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 ...
7
votes
2answers
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. ...
1
vote
1answer
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 ...
1
vote
1answer
21 views
Is my regular expression and finite automata diagram for this state table correct?
So i have some theory of computer science homework and I'm struggling with this question currently. I am given the following automaton:
$Q = \{q_0,q_1\}$.
$\Sigma = \{a,b\}$.
$q_0 = q_0$.
$F = \{q_0\}...
-2
votes
2answers
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
0
votes
2answers
97 views
Build an FA that accepts only the words baa, ab, and abb and no other strings longer or shorter
I have been trying solve this problem for a while now for a university assignment. I'm required to build a DFA and an NFA for the above question. So far I have been able to solve the DFA but can not ...
2
votes
1answer
51 views
Closure of regular languages under interchanging two different letters
Given any deterministic finite state automata $M$ over any alphabet, I need to construct an FSA $M'$ that accepts the set of strings $M$ accepts, but with two different letters interchanged. For ...
2
votes
1answer
48 views
Is there a bound on possible Dead state in a minimized DFA
I want to know if a DFA is minimized, is there an upper bound on how many dead states are possible when it is in its minimal form, in terms of number of states, etc?
Intuitively, I am thinking that it ...
3
votes
2answers
395 views
Irregularity of $\{ w_1 aa w_2 \mid |w_1| \neq |w_2| \}$
I'm currently struggling to come up with a proof that the following language is irregular:
$$L_2 := \{w_1aaw_2 \in \Sigma^* \mid w_1, w_2\in\Sigma^* \land |w_1| \ne |w_2|\}$$
where $\Sigma = \{a, b\}$....
1
vote
1answer
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.
3
votes
1answer
37 views
Worst-Case Complexity of Quantifiers in Thompson's Construction
My understanding is that an NFA compiled using Thompson's Construction should have a running time that is linear in the length of the input string, with a space complexity that is linear with the ...
2
votes
1answer
438 views
NFA for words which start and end with different letters with $O(\log(| \Sigma |))$ states
I'm trying to build a NFA for the following language
$ L = \{ \sigma_1 \sigma_2 \sigma _3 \ldots \sigma _n \mid \sigma _1 \neq \sigma _n \}$.
The catch is that for $ \Sigma $ such that $ |\Sigma|=2^k $...
2
votes
1answer
63 views
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 ...
0
votes
1answer
20 views
Converting along regular expression to NFA
I have the following regular expression for the set of all strings such that each block of five consecutive symbols contains exactly two 0's (consider the alphabet to be {0, 1}):
(0+1+ϵ)4+(11100+ϵ)r(...
0
votes
1answer
21 views
NFA: each block of five consecutive characters contains at least two 0's
How can I find an NFA for such a language, considering the alphabet to be {0, 1}. I've tried deriving it from the DFA (@Steven) and the regular expression (@Yuval Filmus), but no luck.
2
votes
0answers
42 views
In what bases is the language $a^n$ regular?
Given $a\in\mathbb{N}$, I wondered for what bases $b$ is the following language regular
$$\{a_ka_{k-1}\ldots a_0\mid \exists n\in\mathbb{N},\ a_0+a_1b+a_2b^2+\ldots+a_kb^k=a^n\}$$
I think it's regular ...
0
votes
0answers
19 views
Are there more succint algorithm for translating NFA's to DFA's?
When translating an NFA to its deterministic equivalent, we get an exponential blowup due to the powerset construction method. I tried to search but couldn't find an appropriate question regarding ...
0
votes
0answers
20 views
How to describe this language a* (ba (cf* (g ( f +h )* bf* )* e )* a* )* in words?
I was task to describe this regular expression a* (ba (cf* (g ( f +h )* bf* )* e )* a)* informally.
My attempt at describing it informally = any number of a followed by any number of one b one ...
0
votes
1answer
88 views
Understanding lemma found in proof of quotient construction for DFAs
Lemma 13.6 $p \in F \Longleftrightarrow [p] \in F'$
Proof. The direction $\Rightarrow$ is immediate from the definition of $F'$. For the direction $\Leftarrow$, we need to show that if $p \approx q$...
0
votes
1answer
22 views
Give the Regular-Expression (NFA) with specific Separation Patterns
Question:
Given the RE (or NFA) for the set of all strings over $\Sigma ={a,b}$ such that: a occurs the odd number of times and each pair of a are separated by exactly $2n+2,n\geq 0$ b's.
Attempt:
...
1
vote
1answer
33 views
Doubt in understanding the time complexities of algorithms to recognize regular expressions
I was going through the text Compilers: Principles, Techniques and Tools by Ullman et. al first edition where I came across the following table.
The authors justify the table as follows:
Given a ...
0
votes
1answer
39 views
How do I apply the Pumping Lemma to prove that this language is not regular?
I am trying to teach myself Automata theory. I have hard time with the Pumping Lemma, so I am trying to work through examples. I stumbled upon this example, but it doesn't have steps how to solve it.
...
0
votes
0answers
41 views
Co-relating the direct algo for $\epsilon-NFA$ to $DFA$ with the chain : $\epsilon-NFA \rightarrow NFA \rightarrow DFA$
I was going through the text : Compilers: Principles, Techniques and Tools by Ullman et. al where I came across the following algorithm to convert an $\epsilon\text{-NFA}$ to $\text{DFA}$
...
1
vote
1answer
49 views
Finding infinitely many Myhill–Nerode equivalence classes [duplicate]
I need to prove the following languages are not regular and I'm having a
tough time identifying the equivalence class that can have an infinite
index.
How would I go about doing these? I know how to ...
1
vote
1answer
66 views
Regular languages closed under prefix operation
Suppose that $D$ is a regular language over an alphabet $A$. How can I prove that the following language is also regular?
$$ \mathrm{LANGUAGE}_2(D) := \{ d \mid d,t \in A^* \text{ and } dt \in D \} $$
...
