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,290
questions
0
votes
0answers
5 views
Finding a finite automata that accepts a language that is the combination of two other languages with their own automata
I'm told that we have two DFA one A and one B both on alphabet $\sum$.
I'm then told to define a DFA (5-tuple representation) with this condition {w | w = $a_i b_i$...$a_k b_k$ and all the $a \in A$ ...
0
votes
1answer
16 views
Proof for palindrome grammar by induction
I can't seem to find a solution
Given is the following grammar for palindromes:
$G_{pal}=\{\{a-z\},\{P\},P,R\}$ with $R:$
$P \to \epsilon \mid a \mid aPa$ for every a $\in \Sigma$
...
0
votes
2answers
17 views
NFA that ends with 0 and doesn't have 11 after the first 0
So as the title says i m trying to find this NFA. So far i thought to make an NFA that "guesses" what comes after the first 0 and i got this:
After some time trying to get rid of all the extra (7 !)...
2
votes
1answer
87 views
Why is this language a regular language?
Came across this in a book, and I'm wondering why the following language is regular?
$$ L = \{a^nww^R: n \geqslant 0, w \in \{a,b\}^3\}$$
Is it correct to say that $$ \{a^n : n \geqslant 0\} $$ is a ...
0
votes
2answers
32 views
Regular expression for a palindrome of finite length?
I have a language $$ L = \{ww^R, w \in \{ab\}^5\}$$
I know this is a regular language because it is finite (since w can only be of length 5). I want to prove it's a regular language, so I'd create a ...
1
vote
1answer
15 views
I'm asked to draw DFA for this {$\epsilon$, 0} however I do not understand what {$\epsilon$, 0} mean
I'm asked to draw a DFA of this {$\epsilon$, 0} but have no clue what it means. Can someone help me understand what the automata is supposed to do?
I know that $\epsilon$ is the symbol for empty ...
1
vote
2answers
22 views
can more than two arrows point towards the same state from other states in a DFA?
Is something like this possible:
You have state A,B,C all pointing towards accepting state D.
Is this allowed?
Where online can I find a list of rules that define how an automata must be drawn or ...
0
votes
1answer
24 views
$\text{DSPACE}(O(1))=\text{REG}$ Proof?
I want to know why $\text{DSPACE}(O(1))=\text{REG}$, especially in the direction of why all languages in $\text{DSPACE}(O(1))$ can be recognized by a finite automaton. I've thought for some time and ...
0
votes
0answers
27 views
Converting CFG to GNF problem
I have a big problem with converting GNF example.
This is my CFG
$
S \to AS\mid BS\mid \lambda\\
A \to aC\mid BCA\mid c\\
B \to AB\mid b\mid \lambda\\
C \to S\mid d
$
I simplified the CFG by ...
2
votes
1answer
18 views
State complexity of converting epsilon-NFAs to NFAs without epsilon transitions
I am well-aware of the result showing that one can convert an epsilon-NFA (that is, an NFA with epsilon transitions) $A$ to an NFA without epsilon transitions $A'$, where $L(A) = L(A')$.
Is there a ...
-1
votes
1answer
24 views
Automata that respect the condition {w|w contains at least two 0s and at most one 1}
we have the alphabet {0,1}.
{w|w contains at least two 0s and at most one 1}
It tried this: (However I'm not sure if it's correct. If it's incorrect why?)
0
votes
1answer
20 views
I'm trying to understand DFAs is my DFA correct in this question if not why?
I have the following alphat {0,1}.
I'm told to draw a DFA which fulfills the following: {w|w starts with 1 and ends in 0}
This is the DFA I came up with.
1
vote
1answer
33 views
How to create a regular expression for this language?
I have a language:
$$ \{a^jb^k \mid j \neq k \text{ and } j \equiv k \pmod 3 \}$$
I want to prove that this language is regular. My first thought was to create a regular expression that accounts for ...
0
votes
0answers
8 views
Are DPDAs accepting on final state equivalent to DPDAs accepting on empty stack equivalent? [duplicate]
Say I have a string x that is accepted by some DPDA P that accepts empty stack. Intuitively it's seems impossible for P to accept any string x.y for any y != epsilon. The below DPDA accepts on final ...
1
vote
0answers
19 views
Chomsky hierarchy for finite state transducers
In this question in the first answer someone mentions a "special transduction hierarchy". I cannot find anywhere anything about it. Could someone point me to resources on this topic?
-1
votes
1answer
40 views
Turning a regular expression into a DFA
i'm studying for an exam i'll have soon and i don't understand how to draw a DFA for a regular expression, i asked my professor by mail but he doesn't asnwer...
In the courses available on my college'...
-2
votes
1answer
21 views
Minimization of automata with dead state
I am supposed to minimize the following DFA automa, which contains dead state:
But after the minimization of the automata, it stayed the same.
Is it correct?
2
votes
1answer
49 views
Two-way finite automaton: How does the automaton remember the state
I have been going through a theory of Two-way finite automatons and I did not understand the given example when there were a DFA A = (Q, Ī£, Ī“, q1, F). the 2-DFA B = (Q āŖ Q| āŖ Q|| āŖ {q0, qN, qF}, Ī£ āŖ {#...
0
votes
2answers
28 views
Turing Machine state going to itself
Hey guys in a turing machine can a state go to itself by reading a letter. For example,
q2 reading a 'c' to go to itself. Is that possible?
Or does it need to read a tape alphabet, such as $ to ...
1
vote
1answer
47 views
Conversion of nfa with self-loop to one without self-loop
For every nondeterministic finite state automata that has self-loop(s), there exists an equivalent nfa that does not have any self-loop. How can we prove this statement in a general basis without the ...
1
vote
0answers
32 views
How to generate a DFA that recognizes a non-regular Grammar
How would you convert the following grammar to a DFA that recognizes its language?
\begin{align}
&G = (\{S,A,B\},\{0,1\}, S, P)\\
&P\colon
&&S\rightarrow A1B\\
&&&A \...
0
votes
1answer
24 views
Multiple paths for a accepting string in NFA?
If a string(w) is accepted by an NFA, then corresponding to w,
can there be multiple paths each starting from the start state and ending at an accepting state?
0
votes
1answer
28 views
Automaton-based model checking on finite traces
I want to check whether a formula in finite LTL is valid on a finite, linear trace.
For infite traces I would create a Kripke structure of the trace and a BĆ¼chi automaton for the negated formula, ...
1
vote
1answer
22 views
Construct regular expression that contains the substring
I need to write a regular expression for the following set of strings on Ī£ = {a, b, c} in which the number of bās is even, and contains abcba as a substring.
So far, the even number of b's can be ...
0
votes
0answers
25 views
If T is a Turing Machine, what are the languages Accept(T), Reject(T) and Loop(T)?
I have the following Turing machine:
I am asked what are the langauges accept(T), reject(T) and loop(T).
This seems to me a trivial question as from the looks of it, accept(T) is the language of all ...
0
votes
0answers
16 views
Construct a DFA with reduced states equivalent to 10 + (0 + 11)0*1
I have found this question in a book. I could convert it into its equivalent DFA. But the problem is with the "reduced state" part. I think the answer given in the book is wrong. What would be the DFA ...
0
votes
2answers
36 views
convert RE to NFA
The Regular Expression i am having trouble with is the following a(b|bcc*)*c. My main concern is what do i do with the c*? I can lay the rest of the diagram correctly (i think) but that part is ...
1
vote
2answers
30 views
Minimisatiom using Myhill-Nerode Theorem
I have recently studied the MyhillāNerode theorem and while applying it to minimize these FSMs, I encountered a problem. Is it always the case that the final states should be grouped together because ...
0
votes
0answers
40 views
Constrained (linear) NFA-epsilon to DFA conversion
Goal: convert NFA -> DFA
Overall goal: see if the intersection of 2 of these NFAs is empty.
This will be done by converting to DFAs then DFA intersection.
input NFA: multigraph between states (each ...
1
vote
1answer
21 views
Path NFA-eplison to DFA conversion
Does a path (as in path graph or linear graph) NFA-epsilon have a simpler or more efficient algorithm other than the subset construction to convert to a DFA? The only simplifications I have come up ...
2
votes
2answers
31 views
Proving non-regular language using the pumping lemma
I would like to verify that the following language is not regular.
I know that if the pumping lemma is not valid then the language is not regular. (but its not enough to prove that the language is in ...
0
votes
1answer
49 views
If L is regular language then each equivalence class is also regular?
L is a regular language. Let's say that E is one of L's equivalence classes - is it true/false that E is also regular?
The equivalence relation is, from Wikipedia: "Given a language L, and a pair of ...
1
vote
1answer
25 views
FA for |w| divisible by 3 or number of zeros divisible by 2
Working on a question were I should construct a deterministic finite automaton for the language
$L=\{w\in \{0,1\}^* \mid |w| \mod 2 =0 \lor |w|_0 \mod 3 =0 \}$
The DFA for the two sublanguages is ...
0
votes
1answer
28 views
What strings does this language accept/reject?
F = {ww | w ā {0,1}^*}
Which strings are accepted and why?
0011
1010
1111
1
vote
2answers
86 views
Over the alphabet {a,b,c,d}, how would i construct a NFA that only accepts strings that end with a letter that is already part of the string?
I've been trying to create a NFA that accepts strings that end with a letter that exists in the string. For example abcdb, cbdd, acac etc. while strings like abc aacd etc are not accepted since the ...
1
vote
1answer
35 views
Languages such that DFA requires $\Omega(c^k)$ states but NFA needs only $O(k)$ states?
Given an alphabet $\Sigma$, let $c=|\Sigma|$. Can a set of languages $\{L_k\}$ be created, such that any DFA for $L_k$ has $\Omega(c^k)$ states and a NFA for $L_k$ exists with $O(k)$ states?
I'm ...
0
votes
1answer
44 views
Convertion from NFA to DFA
I have converted nfa to dfa. But when I checked with some examples, it looks like it is wrong.
...
0
votes
1answer
40 views
Prove that a language is decidable
I need some help to prove that the language is decidable.
$K$ = {$N$ : $N$ is a DFA (Sigma = {a, b, c}) and $L$($N$) contains at least one word in which there is no a}.
It tried to make an algorithm ...
1
vote
1answer
18 views
Clarifying Practicality and Usage of a DFA's Accepted Language
I was reading up on DFA's and their accepted languages when I stumbled across this:
Let a DFA $M$ accept the language $LāĪ£^ā$, DFA $M'$ accepts $P(L)=$ {$wāĪ£^ā|wyāL$ for some $yāĪ£^ā$}.
Since any $wy$...
0
votes
0answers
13 views
Prove if {a^i b^j | i ā¤ j} is a regular language or not [duplicate]
How can i prove if this language is regular or not? (i think is non regular)
7
votes
3answers
720 views
Why does a DFA have multiple final states?
I am taking a course on programming language design and we got to the DFA part. It is known to be formally defined by a 5-tupple but they did not make it very clear to us why a DFA can have multiple ...
2
votes
3answers
106 views
An approach to determine whether language is regular or not?
I have the following problem. I need to determine whether this language is regular or not:
$L:= \{ w \in \Sigma^*: \forall \alpha ā \Sigma, |w|_\alpha \text{ is even or divisible by 3}\}$
$|w|_\...
0
votes
1answer
26 views
Is this a valid DFA for (a|b)*abb?
I'm trying to come up with an alternate DFA for accepting (a|b)*abb than the one present in the dragon book. Here's the one I tried:
It seems valid to me but I'm ...
0
votes
2answers
33 views
How to prove this language is context free?
There's lots of ways to prove a language is not context free. Going through some exercises, I'm stuck at a question that asks me to prove that a language is indeed context free.
$L = \{a^{(n+1)} b^{(...
2
votes
0answers
32 views
can a DFA with only final states be minimized?
I need to construct a DFA for a certain language with as little states as possible.
so far my "best" solution contains 15 states. however, people claim it is doable in 7 states only. I tried for ...
2
votes
2answers
50 views
Usual distances on DFAs (Deterministic Finite Automata)?
I've been searching in the literature for examples of distances defined on the set of the DFAs (or on the set of minimal DFAs) that are defined on a given alphabet sigma.
Since the languages they ...
0
votes
0answers
41 views
Prove that regular languages are closed under Kleene star [duplicate]
Given $L$ is a regular language, how can I prove that $L^*$ is a regular language too?
I've constructed an NFA which contains a new initial state that has an $\epsilon$-transition to the original ...
3
votes
1answer
34 views
Minimizing DFA built on set of words
A set of English words is given.
Is there linear or sublinear algorithm to build minimal DFA for the given dictionary?
I tried different approaches, and they all were concerned with building Trie and ...
0
votes
0answers
12 views
How to write regular expression [duplicate]
The set of all strings over {0,1} such that every block of 4 consecutive symbol contain at least two 0's
Can you guys tell me what is the correct answer for this ?
0
votes
0answers
35 views
McNaughton-Yamada Algotihm (1960) Regular Expression to DFA without passing through NFA
I have a homework problem here. It asks me to use the McNaughton-Yamada algorithm to first convert a regular expression to a DFA, and then minimize this using a partition argument. I can do the latter....
