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,374
questions
3
votes
2answers
36 views
Minimal DFA for $1\Sigma^*0$
What is the minimum number of states required in any DFA to accept the regular language $L$ over $\Sigma=\{0,1\}$ which accepts those strings that start with 1 and end with 0?
6
votes
1answer
43 views
Determine the number of reachable states in a subset construction?
Is there a polynomial time algorithm to determine the number of reachable states in the subset construction of a NFA to a DFA without having to construct the entire DFA?
1
vote
1answer
32 views
Regular Languages and Separating Suffixes
Preparing for the next semester, I wanted to give the following as a homework question, yet after a few attempts, I failed to solve it.
Given a language $L\subseteq \Sigma^*$ and two words $x,y\in \...
2
votes
1answer
53 views
Conversion of $\epsilon$-NFA to a DFA
So, I was watching a video about the conversion of $\epsilon$-NFA to a DFA. In the resulted DFA, she didn't write the state 4 in any successor set of the sets containing the state 3, and her ...
0
votes
1answer
57 views
Conversion of RE to NFA
I've a question regarding this diagram. I'm thinking of adding a new state between q5 and q6 that accepts a lambda value but I'm not quite sure or this diagram is correct?
And in what situation we add ...
4
votes
1answer
43 views
Is there a method to generate the complement of a context-free grammar?
Given the languages $L_0 = {w \in \{0,1\}^*}$ such that $w$ is a palindrome and $L_1 = {w \in \{0,1\}^*}$ such that $w$ is not a palindrome, meaning $L_1$ is the complement of $L_0$, we want to find ...
4
votes
2answers
804 views
Why is this automaton considered DFA?
So I was watching this video https://www.youtube.com/watch?v=ZjjAbFxjxLQ and the guy was explaining why the top automaton is NFA (because the initial state doesn't know what to do if the input string ...
0
votes
1answer
74 views
What does 'Describe the language of this automaton' mean?
I've been asked to do this as part of an assignment. Here is the automaton:
I understood it as describing in terms of the 5 tuples so I wrote:
The states are as follows: Q = {A, B, C}
The alphabet ...
2
votes
1answer
77 views
Language Containment of Automata
If we are given an NFA and a DFA, can we determine if there exists a string accepted by the NFA and rejected by the DFA and vice-versa. What complexity class would these problems fall into?
0
votes
0answers
53 views
Possibly empty string in a DFA
I am trying to construct a DFA with this language L - all strings consisting of 0ās followed by a (possibly empty) string of 1ās followed by a (possibly empty) string of 0ās. I made the start state ...
2
votes
1answer
53 views
Minimal DFA accepting strings whose length is divisible by $x$ or $y$
Consider the language of all strings whose length is divisible by either $x$ or $y$, where $x,y \geq 1$.
After trying various values of $x$ and $y$, I noticed made the following observation:
If one ...
2
votes
0answers
22 views
closure property violated by palindrome language
It is well established that palindrome language is non-regular. The one way to prove it is by means of pumping lemma. The other way is violating the closure properties of regular language. The ...
2
votes
1answer
32 views
Why can PDAs have infinite stack but FSMs cannot have infinite state?
A Finite State Machine cannot accept the language
$$L = \{ 0^n1^n \mid n > 0 \} $$
because it will require infinite amount of memory to remember the number of zeros. But a Push Down Automaton can ...
4
votes
1answer
124 views
Kleene's Theorem and TMs
I wanted to know that based on Kleene's theorem (a language is regular iff some FSA recognizes it), does every regex have a TM (Turing machine) that halts on exactly the same language?
Is this ...
0
votes
0answers
21 views
PDA Explanation
{a^2i.b^3i | i ā„ 0 }
How would I draw this? I just started learning about pda's and I'm not sure where to start. I've looked at youtube videos explaining pda's but I'm still not understanding how to ...
0
votes
1answer
39 views
Myhill-Nerode classes for a Language $L_k = \{x1y | x \in \{0, 1\}^*, y \in \{0, 1\}^{k-1}\}$
This problem is from an exercise sheet so it would be nice if you could guide me to the solution.
The problem:
For $ k \in \mathbb{N}\setminus\{0\}$ let
$$L_k = \{x1y | x \in \{0, 1\}^*, y \in \{0, 1\}...
0
votes
2answers
64 views
Determine if the language of words with same number of 1's and 2's is context-free or not
$$L_2=\{w \in \{0,1,2\}^* : \text{$w$ has the same number of $1$'s and $2$'s}\}$$
I have tried creating PDA to determine if this was context-free or not. It seems like it would be because whenever a 1 ...
0
votes
0answers
24 views
Draw a CFG (context-free-grammar) that starts and ends with the same symbol yet has odd number of 1's
I figured out that the CFG that starts and ends with the same symbol in alphabet $\Sigma=\{0,1\}$ will be :
S -> 0A0|1A1|0|1|
A -> 0A|1A|š
How can i interpret the odd number of 1's also?
0
votes
1answer
65 views
Turing machine state transition diagram vs finite state machine state transition diagram
If you were given a state transition diagram could you tell, just by looking at the diagram, if the diagram represented a DTM or a DFA (especially if it was unlabeled, just a directed graph)? Would ...
0
votes
1answer
31 views
Create an Finite Deterministic Automata for a regular expression
I want to create a finite state machine that accepts the following language:
$$
L=\{w\in\{a,b\}^* | w \text{ contains abb but not on the first position}\}
$$
So I began by writing a regular expression ...
0
votes
1answer
26 views
How do i prove this language is regular? [duplicate]
I have this language {0+1+0+} and i need to prove it is regular,i had the idea to use the closure properties but i can find any regular languages to unify perhaps.Any ideas?
1
vote
1answer
550 views
What does it mean for a grammar to be LR(0)?
I am unsure what it means for a grammar to be $X$. More specifically, what it means for a grammar to be LR(0).
For part of an assignment I had to form the DFA for a grammar, which I had no issues with....
0
votes
1answer
40 views
Converting Moore to Mealy When first Node has Output
This is a homework question, which I am able to do, except my teacher failed to mention what to do when the very first node has a 1 output. I've looked through online examples, and I'm sure this has a ...
1
vote
1answer
44 views
How do you create a sentential form in a given grammar?
I am given the following grammar:
$$S ::= aBS| abT |a$$ $$T::= d | dT$$$$B ::= da | Ļµ | S$$
I need to decide whether $aBaabda$ can be produced in the given grammar.
I am unsure how the grammar can ...
1
vote
1answer
21 views
Can CFGs generate all languages? Are they (PDAs) finite or infinite state automata?
I was looking for the limitations of a CFG. I think there is some limitation given there are only finitely many states of a PDA (or non-terminals in a CFG).
I suspect that languages like $\text{L} = \{...
0
votes
1answer
57 views
Convert finite automata to regular expression
I am trying find the regular expression that describes the finite automata in the image below.
Given the following finite automata
which of the following regular expressions describes the same ...
2
votes
2answers
36 views
Regular language is closed given transposition of rightmost character to leftmost
It would appear straightforward to show that a regular language is closed given the transposition of the rightmost character to the front. However after drawing a few sample DFA for the phenomenon, I'...
0
votes
0answers
10 views
I'm having some trouble converting a FA to a RegEx [duplicate]
I was reviewing some of the material that I found about FA to RegEx and while I was practicing with one or another conversion, I came across this FA that I could not pass to RegEx. Would someone be so ...
1
vote
2answers
40 views
DFA to accept a String containing even number of both A and B, but rejects empty String
I want to draw a DFA to accept a String containing even number of both A and B, but rejects the empty String(Īµ)
I have already drawn the DFA which accepts the above language, without rejecting the ...
1
vote
1answer
35 views
DFA and equivalence relation
I was studying Theory of Computation and I'm kind of lost in solving this problem.
Let $R$ be a relation defined on the set of states $Q$ of a DFA as $q_1Rq_2$ if $\delta(q_1,a)=\delta(q_2,a)$ for ...
1
vote
2answers
57 views
Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular?
Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular? I do not think it is. I recently posted a question and from there I was thinking if this language is regular.
If we assume on the contrary, then there ...
1
vote
2answers
24 views
Operations without common elements can not be generated using a finite state automata
I heard that some operations involving regexes that do not have common elements can NOT be generated using a finite automata. I do not remember what it was, where it was from, can anyone tell me what ...
1
vote
0answers
15 views
Is that a regular express? Proof using closure properties or pumping theorem [duplicate]
I am studying regular express. I understand how to proof a xa ya. However, I don't know how to proof the below problem. Please help me.
L = { xa yb | a ā b }
0
votes
1answer
76 views
Is (a+b)* and (ab)* same in finite automata?
Regular language of (a+b)* and (ab)* are:
(a+b)* = { Īµ, a, b, aa , ab , bb , ba, aaa, ...}
(ab)* = { Īµ, a, b, aa, ab, ba, bb, aaa, ... }
I am new to Finite automata and this simple notion is ...
0
votes
2answers
37 views
What does this language notation specify?
I am given this exercise:
Let L1 ={akbk : k > 0} and L2={ck : k > 0}. For each of the following strings wi, state and explain whether or not wi ā L1L2.
w1=Īµ
w2=aabbcc
w3=abbccw
w4=aabbcccc
w5=...
1
vote
2answers
36 views
Proving a language with equal occurences of ab, and cd is not a regular language using the Pumping Lemma
I am trying to show that $A = \{w \in \{a,b,c,d\}^{*}|w \textrm{ has equal occurences of } ab \textrm{ and } cd\}$ is not regular by using the Pumping Lemma.
My idea here was to use the string $ s = (...
1
vote
1answer
33 views
Applying the Pumping Lemma to aspecific string
Given the language $ A = \{w \in \{a,b\}^{*} | w = w^{R}\}$ (i.e. palindromes using the symbols $a, b$), I am trying to determine if the Pumping Lemma can be applied to strings of the form $s = a^{2p}$...
0
votes
0answers
47 views
NFA recognizing strings in $\{0,1\}^*$ that have two zeros separated $4i$ characters, for some $i\geq1$
I am trying to design a nondeterministic finite automaton that recognizes the language of strings in $ \{0,1\}^{\ast}$ that have two zeros separated by a string of length 4i, for some $i \geq 1$.
Let $...
0
votes
2answers
22 views
string concatenation vs language concatenation
What exactly is the difference between
$$
C = \{a^*\}\{b\}\{a^*\}\{b\}\{a^*\}\{b\}
$$
and
$$
D = \{a^nba^nba^nb | n \geq 0 \}
$$
It is known that D is non-regular and C is regular, but I am not sure ...
2
votes
2answers
51 views
How to we prove if a right linear language is ambiguous?
Considering the following language as an example:
$$\begin{align}
S &\rightarrow aS \mid bA \\
A &\rightarrow bA \mid aB \mid aD \mid \varepsilon \\
B &\rightarrow aB \mid \varepsilon \\
D ...
0
votes
1answer
34 views
Read regular Expression from NFA
Good evening everyone!
Can someone help me with the following task?
So we have this NFA:
I was supposed to create a regular expression out of it. Now the solution says: $a^{+}b^{+}(c|ca^{*}b^{+})^{*}$...
1
vote
1answer
119 views
What is the the pumping length for the regular expression (0+0001)((1111)*+(00)*)
I have this assignment question to find the pumping length of a regular language (L). The regular expression for the L is given as
$(0+0001)((1111)^*+(00)^*)$
What is the length of the longest string ...
2
votes
3answers
45 views
How to use DFA/NFA to prove the language {$0^n 𝑥1^𝑛$ | x ā Ī£*, n ā„ 1} is regular?
I'm trying to prove the language L = {$0^n š„1^š$ | x ā Ī£*, n ā„ 1} is regular, but don't know how to present it in a DFA/NFA.
I'm thinking to have n+1 states in a NFA, with the start state as the ...
0
votes
1answer
27 views
minimum number of states in cross product of two minimum DFAs
If FA1 and FA2 are 2 DFAs with minimum number of states. I want to find cross product DFA (FA1XFA2). Will the cross product DFA obtained from 2 minimum DFAs also have minimum number of states(num of ...
1
vote
2answers
68 views
How to prove that concatenating a language A and A* is commutative?
Suppose we have a language $A$. I want to prove that $AA^*$ is commutative. I know that this expression equals $A^+$, but I'm not sure how to go about a proof yet. This is my attempt so far.
If $A$ is ...
0
votes
0answers
87 views
Generalization of automaton - Sipser example 1.33
I am trying to construct a nfa that generalizes Example 1.33 found in the book Introduction to the Theory of Computation by Sipser, but I am quite sure
that my transition function is wrong. I'd like ...
0
votes
0answers
30 views
Building an NFA where where proceeding part of string has same or more 1's
Having trouble figuring out a NFA for the following language, the objective is to use only 3 states:
$L = {\{1^ky : y \in \{0,1\}^* }\text{ and y contains atleast k 1's, for k} \ge 1 \}$
I have got to ...
3
votes
1answer
179 views
Complete explanation of state elimination methods [duplicate]
I'm so sorry if this question is too general, but I need to understand the general process of the "State elimination method".
In other words, what is the general idea, and what is the ...
1
vote
2answers
45 views
How are useless states created NFA to DFA
So I understand how to convert an NFA to a DFA, however my question is, on a conceptual level, how and why are useless states created, and how can you (if there is a way) convert an NFA to a DFA ...
0
votes
1answer
137 views
Understand the DFA: accepting or not accepting “aa” or “bb”
I want to discuss the strings accepted by couple of DFAs:
DFA in Figure 1 has 3 final states. It looks like that it accepts both the substrings "aa" (q0q3q0q1) or "bb". So this is ...
