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.
0
votes
0answers
37 views
Minimization of DFA 3 inputs Table Filling Method
I do understand how minimization of DFA works where there are 2 words lets say $\{a, b\}$. However, I came across this minimization of a DFA over the language of $\{a, b, c\}$ $\left(\Sigma, \{q_0, ...
1
vote
2answers
29 views
How to convert this DFA with multiple final states to a regular expression? (State elimination method)
So I have a DFA which I would like to convert to a regular expression. As you can see it has multiple accepting states and the start state has incoming input 'a' from q2 and 'b' from q4.
I want to ...
1
vote
1answer
37 views
Language of all sequences of permutations whose product is the identity
Let $\Sigma$ be the set of all permutations in $S_n$. What is the minimum number of states in a DFA accepting the language of all words over $\Sigma$ which multiply to the identity permutation?
For ...
0
votes
1answer
36 views
How to minimize this DFA with already merged states?
The original nondeterministic FSA I have is:
After converting this to a DFA I get:
If I use the Myhill-Nerode theorem on the current DFA, I get all pairs marked, so this is already minimized. But I ...
1
vote
1answer
34 views
Proving that no 2-state DFA decides the language A = {x ∈ {0, 1}* | bnum(x) is divisible by 3}
I am doing a problem where I need to prove that no 2-state DFA decides the language
A = {x ∈ {0, 1}*| bnum(x) is divisible by 3}.
It's seems pretty obvious at first, because aren't there only 4 DFA's ...
3
votes
2answers
92 views
Why is every finite language A ⊆ Σ* regular
So I've been doing regular languages a while and still need a better understanding of why all finite languages A ⊆ Σ* are regular? Is there a formal proof of it or is it just because a DFA can ...
3
votes
2answers
43 views
Regular expression for binary words with 1 in the middle
Given the alphabet $\{0,1\}$, generate a regular expression with the following language: $$ \{w\in \Sigma^* \mid w \text{ has odd length and its middle symbol is }1\}. $$
I'm having trouble finding a ...
-5
votes
0answers
19 views
Should we still study finite automatan? [duplicate]
Can anybody help me with this homework question?
In the era of information, technology changes at drastic speed, and the same is observed in Computer Science and Information Technology. The need ...
-2
votes
1answer
105 views
Regular Expression and Finite automata in field of compiler construction [closed]
In the era of information, technology changes at drastic speed and same observed in Computer Science / Information Technology field. Need of intelligent compilers for high level languages are ...
0
votes
1answer
44 views
DFA for $L = \{y \in (a+b)^* \mid ||y|_a - |y|_b| \leq 10 \}$
$L = \{y \in (a+b)^* \mid ||y|_a - |y|_b| \leq 10 \}$
Any idea? I have problem with this kind of task.
1
vote
1answer
15 views
What does it mean to take a union of a transition function with a starting state?
$$
\delta(q,a) = \begin{cases}
\delta_1(q,a) & q \notin F_1 \text{ or } a \neq \lambda \\
\delta_1(q,a) \cup \{q_1\} & q \in F_1 \text{ and } a = \lambda.
\end{cases}
$$
Look at the second ...
0
votes
1answer
44 views
Prove $ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $ is regular or context-free or neither
$ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $
Exercises: If the language L is regular (build a DFA or regular expression)
else if the language L is context-...
1
vote
1answer
36 views
State-elimination on FSA, after epsilon-removal construction
I want to define the language of this FSA with a regular expression. I have learned that by state-elimination, I would be able to find a regular expression.
But there are already some epsilon ...
-3
votes
0answers
26 views
In what complexity class is the problem of checking whether two NFA states are equivalent? [closed]
That is, check if two NFA states accept the same language?
1
vote
1answer
28 views
Proving existence results
I'm doing a problem where I need to prove that there is a language A ⊆ {0, 1}* with both of the following properties:
(i) For all x ∈ A, |x| ≤ 5.
(ii) Every DFA that decides A has more than 8 states....
0
votes
1answer
25 views
FSMs and Boolean dynamical systems
Is it not always possible to represent a Finite State Machine (FSM) by a Boolean dynamical system?
A Boolean dynamical system is defined by a Boolean map $F\colon B_{0}^n\to B_{0}^n$ (where $B_{0}$ ...
1
vote
0answers
26 views
Algorithm for DFA accepting any string with ending with a particular substring
Is there any possible general algorithm for constructing a DFA such that it accepts any string, which has a given sub-string in the suffix(end) for any given language. The algorithm should directly ...
0
votes
2answers
29 views
Is a language that sits between two regular languages also regular?
Suppose that L0, L1, L2 are languages over the same alphabet and that
L0 ⊆ L1 ⊆ L2.
Is it true that if L0 and L2 are regular, then L1 must be regular as well?
...
2
votes
1answer
23 views
Is it possible to denote “any single alphabet symbol” in an FSA state diagram?
This is a possible duplicate of the following (but not sure it answered my question):
Is it possible to support .(any symbol) or \d, \w, \W in DFA
My professor is asking for a finite automata state ...
0
votes
1answer
36 views
Maximum number of words in deterministic finished automata with k-states [closed]
I have exercise:
We have a given finished deterministic automata. It has 5 states and is
based on the alphabet {a, b, c}. It can create n different words (we assume that n <
inf). What maximum ...
1
vote
1answer
33 views
Difference between methods of converting from finite state machine to regular expression
I have a question about method that I saw on internet and method that my professor showed me. I have this finite state machine:
...
2
votes
1answer
56 views
Density of regular language containing all squares
I am self studying automata theory and I found a problem set from an old class I took a few years ago, but I have no clue how to solve the following problem, any help would be appreciated.
Suppose we ...
0
votes
1answer
33 views
How can I find the Myhill-Nerode classes for the language A?
I have the following task (no homework).
Find all equivalence classes of the Myhill-Nerode relation of the language $$ \mathrm{A} \triangleq\{w \in \Sigma^{*} | w\text{ does not end with }01\}\,. $$...
1
vote
1answer
38 views
Why is this not recognized by a DFA?
I am still confused over my professor's explanation on why this problem is not a DFA.
The Problem: Explain why $L = \{p^kq^k \mid k>0\}$ cannot be recognized by a DFA
My professor explained it as ...
1
vote
2answers
44 views
Pumping Lemma. Why is there a word w in L for infinite languages with n≤|w|≤2n
The following comment on an other question says that if we have an infinite language L that satisfies the pumping lemma for regular languages then we have a word with n≤|w|≤2n which is in L. (n is the ...
1
vote
1answer
35 views
How to build a finite automaton for right quotient of a regular language?
Let $L$ be a regular language over $\Sigma=\{a,b,c\}$. Build a finite automaton for $L/\{a\}$.
Because $L$ is regular then a DFA exists for it: $A=(\Sigma, Q, q_0, F, \delta)$.
Let $M$ be a finite ...
1
vote
1answer
39 views
If a deterministic finite automaton recognizes a language, must that language contain every accepting input?
May a DFA recognize a language which is a proper subset of the set of all accepted inputs?
For instance, if there is a DFA which decides if an input $W$ has $w_0 = w_n$, can it recognize a language $...
0
votes
0answers
23 views
DFA that accepts word and its reverse [duplicate]
The problem is as follows: design DFA over an alphabet {a,b}, that accepts a language: L = {$xwx^R$ | $x \in \{a,b\}^+, w \in \{a,b\}^+$}
I have no idea how to remember the first word to be able to ...
0
votes
0answers
10 views
NFA to DFA with Epsilon transition [duplicate]
Does my first following of the NFA-DFA Algo look correct? The two tables are me following the algorithm to convert...
And for the second problem how do I deal with epsilon transition while following ...
0
votes
1answer
28 views
DFA - unsigned int with digits in non-decreasing order
I was hoping someone could help me in understanding how to achieve a DFA here. The question is how I would create a DFA that accepts unsigned decimal integers whose digits are in non-decreasing order, ...
0
votes
1answer
38 views
Why are finite automata defined as ordered $n-tuples$ and not as sets?
First off, I should mention that I am a new contributor on this site and as such, please bear with me if this has been asked and answered before. I searched to the best of my ability to find similar ...
0
votes
0answers
26 views
Space complexity for accepting word decision problem of DFAs
It is well known that the the decision problem $w \in \mathcal{L}(M)$ for a DFA $M=(Q,\Sigma, \delta, q_0,F)$ is in $\mathcal{O}(|w|)$. To proof this we assume that the successor state computation can ...
3
votes
2answers
209 views
Is it possible to convert LBA into DFA?
Today I learned about an abstract class of machines called linear bounded automata.
It is intended to model real-world computers that have a limited amount of memory. I have always thought that real ...
0
votes
1answer
42 views
Can the pseudo-random-sequence generator be described as a finite state automaton?
I am thinking some real examples of FSAs in order to help me know how to use the model of the FSA. As I know, the pseudo-random-sequence generator should be a kind of DFAs or FSTs . But I cannot ...
1
vote
1answer
39 views
Intersection of two incomplete DFAs
Let assume that I have the following two automata A1 and A2 :
I have to do the intersection of the two, so I did this :
My question is related to the "∅". If I have two incomplete automata without ...
0
votes
0answers
14 views
What are some differences between regex (FSM) in computer science with regex in programming? [duplicate]
Computer science has automata theory with lessons on regular expressions and FSM. How are these different from regex engines used in programming such as C++, Perl, PHP etc.?
I would like to know some ...
2
votes
2answers
382 views
Can a Formal Language be of a type (RE, REC, Regular, etc) for one TM, but of a different type for another?
I'm new to the study of formal languages, and I wondered if languages of a certain type are objectively of that type (RE, REC, regular, etc), or if their type varies on their context? I had this ...
3
votes
2answers
58 views
The complexity of the reachability-coreachability analysis of a finite state machine
Let $A = \{\Sigma,Q,\delta,q_{0}, Q_{m}\}$ be a finite state machine (FSM). A state $q \in Q$ is reachable if there exists a string $s \in \Sigma^{*}$ such that $\delta(q_{0},s) = q$. The state $q$ is ...
1
vote
0answers
26 views
RO turing machine with finite memory
Consider the following:
A weak TM is a TM with finite tape in size $k$ which can only read its input values. note: the tape size does not include the input length.
I need to determine whether if the ...
-3
votes
2answers
45 views
DFA accept 00 as a substring
How can design this question if we have an equation like that
={wxw | w={0,1}* , x=00} accept 00 it means not contain 000,001,100, but accept all these {00,1001,110011,001000001.....}. Thank you for ...
2
votes
1answer
36 views
finding separating words (Nerode)
i have found the equivalence classes of given $R_L$ and i need to find the separating words between the equivalence classes(which i don't know how to do). would appreciate if you could explain to me ...
5
votes
2answers
228 views
Constructive proof to show the quotient of two regular languages is regular
I have a question regarding the quotient of two regular languages, $R$ and $L$.
I saw the answers to this question: are regular languages closed under division
and the proof sketch is not ...
1
vote
1answer
33 views
Are there strings which get accepted only by PDA by empty stack and not by PDA by final state, and vice versa?
Can the same PDA accept both by final state and empty stack in the sense that there are some set of strings that are getting accepted by empty stack, while other set of string by final state and ...
1
vote
2answers
35 views
Does this DFA describe this regular expression?
For the expression (ab)*ba I came up with the following (very poorly drawn):
However, this was not the correct answer - apparently the solution requires five ...
2
votes
2answers
55 views
How to prove certain parts of one regular language restricted by another regular language is also regular?
I’ve encountered the following difficult question that I don’t know how to solve.
$L_1$ and $L_2$ are regular languages over the same $\Sigma$. $$\begin{align}L^\wedge=&\{σ_1σ_2...σ_n\mid n\ge1, \...
0
votes
1answer
20 views
Given set of grammar rules, how to find if they correspond to Context-free or unrestricted
Given set of grammar rules, how to find if they correspond to Context-free or unrestricted?
Just for Understanding (don't solve the below one),
eg:
\begin{align}
S &\rightarrow B/A, \\
1B &\...
2
votes
1answer
54 views
How to draw NPDA for words whose number of b's is strictly more than that of a's but strictly less than twice the amount
I know that CFG for $$ \{a^{m}b^{n}\mid m\leq n\leq 2m \}$$ is
$$ S\rightarrow ab/abb/aSb/aSbb $$ but I am not able to tweak it in such a way that it is strictly in between m and 2m and not equal to ...
0
votes
1answer
16 views
Construct context-free grammars that generate for the languages L(G) = {01(110)^n 10 (11)^n : n >= 0}
I have given this question as home assignment. I tried a lot to solve it but couldn't found any solution. Please help
Thanks in Advance!
1
vote
1answer
32 views
If a DFA were implemented as a circuit, what would the empty string correspond to as input?
Say we have a DFA like the one shown below that accepts the empty string, $\varepsilon$.
Also suppose the functionality of this DFA has been implemented as a circuit so that an led lights up ...
1
vote
0answers
21 views
Decision problems involving finite automata
A finite automaton (FA), A, may accept or reject its own encoding, {A}. A machine, M, can be written that accepts {A} iff A rejects {A}. Turing gave a famous proof that M is not an FA. The proof ...
