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,363
questions
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
36 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
1answer
33 views
Cannot determine if this language is context-free or not
L2={w e {0,1,2}* : 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 is pushed onto the stack,...
0
votes
0answers
14 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?
1
vote
1answer
42 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
24 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
24 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
536 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
39 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
37 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
17 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
44 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 ...
1
vote
2answers
31 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
39 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
32 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
0answers
21 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 ...
0
votes
0answers
14 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
25 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
31 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
33 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
31 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
40 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
37 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
33 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^{+})^{*}$...
0
votes
1answer
108 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
42 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
24 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
55 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
86 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
29 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 ...
1
vote
1answer
73 views
Expert 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
37 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
78 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 ...
2
votes
1answer
12 views
Sufficient condition for $xy^*z \subseteq L$ for a DFA with $n$ states
In chapter 2 of the New Turing Omnibus, the author considers an unknown finite automata with 6 states. Through trial and error, it is deduced that the words 0101, 0100101, 0100100101 are accepted. It ...
1
vote
2answers
14 views
PDA for a language where the second part is not the reverse of the first part
I came across an exercise for constructing a PDA for the following language:
$$L = \{ncm \mid n,m\in\{a,b\}^* \text{ and } n \ne m^R\}.$$
Where $L \subseteq ({a,b,c})^*$
So $n$ and $m$ are both a ...
1
vote
1answer
19 views
A regular language derived from another
This is similar to a previous question I asked, but doesn't seem aminable to the same technique. Given a regular language $A$, show the following language is regular:
$$
\{x|\exists y \; |y| = 2^{|x|} ...
0
votes
1answer
35 views
Can this language be called regular?
Recently, I was facing some problems in effectively proving the following :
Consider the alphabet Σ ={0,1,2,...,9,#}, and the language of strings of the form x#y#z, where x,y and z are strings of ...
0
votes
2answers
67 views
How can I efficiently construct a CFG from a language
I am new to CFG's and automata in general and I came across an exercise where I needed to construct a CFG for the language {a^m b^n | n <= m + 3}.
So m can be infinitely bigger than n but n can ...
1
vote
1answer
31 views
Regularity of a language constructed from a know regular language
I'm working through so textbook questions on regular languages, and came across a problem that amounts to showing the following language is regular, given that $A$ is a regular language:
$$
\{x|\...
1
vote
1answer
28 views
Construct a DFA recognizing a language $L$ that has exactly $I(L)$ states
Let $L$ be a language, and consider the following relation $\equiv_L$ on strings:
$s_1 \equiv_L s_2$ if and only if, for every string $w$, we have that $s_1w \in L \Leftrightarrow s_2w \in L$.
This is ...
1
vote
1answer
68 views
Clarification on an Hopcroft book DFA minimization example
At page 156 there is an example on how to find the distinguishable states for the following automaton:
The following table shows the distinguishable states:
By applying the given definition for ...
1
vote
1answer
114 views
Check if a NFA accepts a string of non-prime length
Given a nondeterministic finite automaton $A$, give an algorithm that checks whether the language $L(A)$ decided by $A$ contains a string whose length is a composite (i.e. not prime) number.
My ...
0
votes
1answer
52 views
What language does this deterministic finite automaton accept?
Been mulling over this one for hours, my initial thought was { w ε {a,b}* | w is empty, or ends with either ab or ba} but that's clearly wrong as neither aba nor bab are accepted by the automaton. If ...
2
votes
1answer
61 views
Extracting regex submatch boundaries without backtracking
I'm attempting to develop from scratch a simple regex engine. I would like for my engine to have the ability to report, "The regex matched on a substring of this line starting at index and ...
4
votes
1answer
161 views
Show $L = $ { w $\in (a,b) ^* $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$ is regular
I try to show that this language is regular:
$L = $ { w $\in \ (a,b) ^ * $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$
If I build a NFA and run on it every substring of w (skip other letters ...
3
votes
2answers
111 views
Is it possible to construct a finite state automata for a decimal adder?
Suppose the strings are of the form x#y#z , where x,y,z are strings formed from the alphabet $\Sigma=(0,1,2,3,4,5,6,7,8,9)$ . The language is accepted if x+y=z is satisfied, for example : 56#65#121 is ...
-2
votes
1answer
46 views
running RAM on a given input
I understand how RAM commands work but I am unable to understand how we use a given input string and find the output. For instance,
there's a Random Access Machine which has an input {0,1}*. The ...
