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,460
questions
3
votes
2answers
377 views
If regex describes FSAs, what string formats describe Turing machines?
(Topic summary under the line.)
Regex, at least the formal definition featuring only | and *, is used to describe words accepted by a given FSA, but it can be transformed into the corresponding state ...
2
votes
1answer
52 views
How to prove the same states are repeating in Synchronizable DFA?
I'm trying to prove the if $𝑀$ is a $𝑘$-state synchronizable DFA, then it has a synchronizing sequence of length at most $𝑘^3$. first I have to prove that if a string syncs two states, then its ...
0
votes
1answer
59 views
How to describe the language of an automaton in plain English?
How do I describe the following automaton in plain English?
The only thing that I can think about when explaining in plain English would be the states, alphabet, start, accepting state, but I think ...
3
votes
1answer
40 views
Efficient algorithm to find a rejecting input of an NFA
I cannot think of a PTIME algorithm to find a rejecting input of an NFA. While it is possible to efficiently find a rejecting input for a DFA, converting an NFA to DFA is too expensive.
The algorithm ...
0
votes
1answer
21 views
Question about an answer related to designing an ASM for a sequence detector
The question says:
Design a sequence detector that searches for a series of binary inputs to satisfy
the pattern 01[0*]1, where [0*] is any number of consecutive zeroes. The
output (Z) should become ...
2
votes
2answers
54 views
Prove the language $\{x \in \Sigma^* : \exists w \in \Sigma^* \ xww \in L \}$ for regular language $L$ is regular
Let $\Sigma=\{0,1\}$ and $L$ be a regular language. Prove that
$$Z(L) = \{x \in \Sigma^* : \exists w \in \Sigma^* \ xww \in L \}$$
is a regular language.
I tried to build a NFA based on the DFA that ...
-2
votes
2answers
24 views
Drawing transition diagram from transition table
I have a DFA transition table like
\begin{array}{cc|c|c}
& & 0 & 1 \\ \hline
\to & p & qs & q \\
* & q ...
1
vote
2answers
57 views
How is CLR(1) grammar more powerful than LALR(1) grammar
I am unable to understand how Canonical LR(1) grammar is more powerful than LookAhead LR(1). Both have lookahead symbols in their items and works almost similarly, so how can CLR(1) derive a larger ...
-2
votes
1answer
47 views
Finding the language generated by this grammar
I'm having problems with this. Can someone help me please.
Find the language generated by this grammar over the alphabet $\{0,1\}$:
$S\rightarrow BAB\mid CAB$
$BA \rightarrow BC$
$CA \rightarrow AAC$
...
1
vote
1answer
38 views
How to draw Turing machine for multiplying a number by 2 in base 10
I'm trying to design a turing machine that given a number in base 10 multiplies it by 2.
The problem seems trivial if the number is represented in binary so what I've thought is try to convert it from ...
1
vote
1answer
39 views
Proof that for every $k > 1$, there exists a language $A_k \subseteq \{0, 1\}^*$ s.t. a DFA accepting $A_k$ has $k$ states but no less
I am trying to prove that for every $k > 1$, there exists a language $A_k \subseteq \{0, 1\}^*$ such that a DFA accepting $A_k$ has $k$ states but no less.
I thought about proving this in two ways: ...
3
votes
1answer
94 views
NP completeness of deciding whether a set of examples, consisting of strings and states, has a corresponding DFA?
I'm working on a textbook problem, 7.36 in Sipser 3rd edition. It claims that if we are given an integer $N$ and set of pairs $(s_i, q_i)$, where $s_i$ are binary strings and $q_i$ are states (we are ...
1
vote
1answer
13 views
NFA designing for strings starting with $01$
The question was asked
Construct an NFA with set of all strings that start with $10$.
The solution provided to me is
But my question is what if the automaton receives an input $0$ at the starting? ...
1
vote
1answer
23 views
Possibility of using loops instead of traps
Draw DFA for the language of all strings starting with $a$ and ending with $b$.
Now what I have done is
Here I used q3 as a trap.
But could I do this instead?
I have not used trap in the 2nd ...
0
votes
1answer
36 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 ...
4
votes
1answer
42 views
Maximal minimal DFA for some language of n-bit strings
Notation: $M$ is a DFA; $L(M)$ is the language accepted by $M$; $\min(M)$ is the minimal automaton equivalent to $M$ derived from a minimization algorithm such as the Hopcroft algorithm; and $|M|$ is ...
0
votes
0answers
23 views
How NFA decides how to break up a string?
If we have a language K, that word w=uv, accepts.
$K= \{{w \in \{a, b ,c\}^*: \ \vert u \vert_a \ \text{is not divisible by 3}}\}$. Can we land strings like aaaa ...
0
votes
0answers
32 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
31 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
37 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
21 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
1answer
35 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
62 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
35 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
28 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
50 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
25 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
40 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
38 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 ...
0
votes
1answer
42 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
17 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
38 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
17 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
24 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
128 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
159 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
25 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
23 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
109 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
53 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
400 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
36 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.
