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
2answers
46 views
How to convert NFA with null moves to NFA without null moves?
I am converting NFA with $\varepsilon$-moves to the NFA without $\varepsilon$-null moves. I understand that if, there is a $\varepsilon$-move between, $q_i$ and $q_j$, then all edges from $q_j$ have ...
1
vote
1answer
58 views
Converting an NFA to regex using GNFA algorithm?
So I've been trying to crack this for a long time and almost feel like I am going in loops about this question.
Given the following NFA:
Using the GNFA algorithm get the regular expression.
I ...
3
votes
2answers
93 views
Show that it is undecidable if two Turing Machines accept the same language
I was asked this question at an interview, and couldn't answer it, and would like to know how it is 'shown' that two Turing machines which accept the same language is undecidable. This is not a ...
2
votes
0answers
25 views
Classes of NFAs which allow efficient subset testing or unambiguity conversions
I'm doing some research regarding NFAs and inclusion problems with them. I know that in general, the inclusion problems, and converting to an unambiguous NFA, are both PSPACE-complete.
I'm wondering, ...
3
votes
1answer
42 views
Optimal upper bound on the number of states in the complement of an NFA
I have my own version of lex and I would like to add the complement operation. Derived from that I can then add the intersection and difference also. My version ...
1
vote
4answers
91 views
Designing a regular expression for the set of all binary that contain strings without a particular sub string (i.e. $110$)
I'm still a newb at designing regular expressions without particular sub strings
for the case of a regular expression without sub string $110$ I Was thinking of: ...
0
votes
0answers
23 views
FSP model of a belt system
I am building a FSP Model for a belt system. I have a producer that deposits and the consumer that collects items placed on the belt. I can model if for a single item but not for more than that. The ...
1
vote
1answer
42 views
Is the language $a^{3}b^{+}$ the same as $\{a^{3}b^{n}, n \geq 1\}$ ? and what is the result of pumping this?
The regular expression $a^{3}b^{+}$ is indeed regular because we can define an automata $M$. But I see that $\mathcal{L} = \{a^{3}b^{n}, n \geq 1\}$ may generate the same strings, but using the ...
3
votes
2answers
125 views
Prove that $L_1$ is regular if $L_2$, $L_1L_2$, $L_2L_1$ are regular
Prove that $L_1$ is regular if $L_2$, $L_1L_2$, $L_2L_1$ are regular.
These are the things that I would use to start.
As $L_1L_2$ is regular, then the homomorphism $h(L_1L_2)$ is regular.
Let ...
2
votes
1answer
40 views
Cartesian construction of PDA and DFA
How would I go about using Cartesian construction to find the intersection between a PDA and a DFA?
Is there another term for Cartesian construction? Would it be similar to the procedure for finding ...
0
votes
1answer
41 views
Simple FSM question
Considering this FSM:
Can someone explain me why the grammar is not:
$S \rightarrow aA$
$A \rightarrow aA \mid bB \mid \varepsilon$
$B \rightarrow bB \mid \varepsilon$
Why does A not have a ...
6
votes
4answers
226 views
Can an FSA count?
This may be a silly question. It seem clear that an FSA, since it is finite, can only count the number of symbols in its input string up to a number bounded by the number of its states. But now ...
1
vote
1answer
51 views
Given an NFA A and a regular expression B, is the problem of determining L(A) = L(B) decidable?
I have an exam coming up and I need help with the following homework:
Given an NFA $A$ and a regular expression $B$, consider the problem of determining if $L(A) = L(B)$. Is this decidable? Prove ...
4
votes
2answers
110 views
Why is the following language not context-free?
$L = \{a^n b^m | m \not= n^2 \}$
I guess I need to use Pumping Lemma for CFL in order to prove this. But I'm stuck.
Assuming that $ a^n b^m = uvxyz$, we know that $v$ or $y$ can not have both $a$ ...
5
votes
3answers
120 views
Can a Turing Machine decide if a regular expression matches all strings of exactly some length $l \geq 1$?
Earlier I asked the question: Can a Turing Machine decide if an NFA accepts a string of prime length?. The answer introduced me to Parikh's theorem, which I've been reading about. The concept of ...
10
votes
1answer
231 views
Can a Turing Machine decide if an NFA accepts a string of prime length?
I want to know if the following problem is decidable:
Instance: An NFA A with n states
Question: Does there exist some prime number p such that A accepts some string of length p.
My belief is that ...
6
votes
1answer
108 views
Difference between the languages accepted by two DFAs with different initial state/accepting states?
Recently, I asked a question on Math SE. No response yet. This question is related to that question, but more technical details toward computer science.
Given two DFAs $A = (Q, \Sigma, \delta, q_1, ...
4
votes
1answer
68 views
A procedure for Topological sort, proof for its correctness
Definition: A preserved invariant of a state machine is a predicate, $P$, on
states, such that whenever $P(q)$ is true of a state, $q$, and $q \rightarrow r$ for some state, $r$,
then $P(r)$ holds.
...
1
vote
1answer
74 views
Union of two automata
I need to find a minimal DFA given the following information:
$ \{a^nb : n\geq 0\} \cup \{b^na: n \geq 1\}$
Now, maybe I'm not seeing this properly, but I don't see how this is possible: the ...
-3
votes
2answers
85 views
Build a FA that accepts the language of all strings of length 4 or more such that the next-to-last letter [closed]
Can anyone solve this?
"Build an FA that accepts the language of all strings of length 4 or more such that the next-to-last letter is equal to the second letter of the input string."
3
votes
1answer
56 views
Difference between pattern matching and pattern searching in terms of DFA/Regex
E.g.
Matching Problem The DFA of regex good is like a chain.
...
3
votes
1answer
92 views
Can we say anything about the complement of a regular language?
Given a regular language $L$, can we say anything about its complement $\overline L$? One thing that is trivial to say is that the DFA's for both languages are equal in size as complementing the ...
3
votes
2answers
202 views
What is the difference between finite automata and finite state machines?
I have used FSM in Digital sequential Circuit designs. But I am unfamiliar with Finite Automata. Can somebody help me in understanding 'basic' difference between the two ?
3
votes
4answers
140 views
Practical application of Finite State Machines
I am looking for practical applications of Finite State Machines like DFA, NFA, Moore, Mealy machines...
It would be helpful if someone point to examples from Linux Kernel. I know that DFA is used in ...
2
votes
1answer
111 views
DFA to regular expression conversion
I was looking at the question How to convert finite automata to regular expressions? to convert DFA to regex.
The question, I was trying to solve is:
I have got the following equations:
$Q_0=aQ_0 ...
1
vote
1answer
40 views
Minimizing Turing machine-like automaton with no final states
I have a deterministic finite automaton which behaves mostly like a Turing machine, with following difference (relevant to this question):
The tape is initially finite.
The automaton can insert and ...
2
votes
2answers
34 views
Definition of uniform boolean circuit
Definition
A family of circuits $(C_{1}, C_{2}, \ldots)$ is uniform if some log
space transducer $T$ outputs $\langle C_{n}\rangle$ where $T$'s input is $1^{n}$. (from ...
1
vote
1answer
114 views
Is The Following Language Regular? [duplicate]
Let $L_{1}$ and $L_{2}$ be 2 languages over the same alphabet $\Sigma$.
$$A(L_1,L_2)=\{x\in \Sigma^*|\exists y,z\in L_2\text{ such that } yxz\in L_1\}$$
Assume that $L_{1}$ is regular and $L_{2}$ ...
1
vote
1answer
82 views
Closure of regular Language - Transition Function : Sipser Proof
I was going through construction proofs for closure of regular languages under union, star and concatenation operation in the book: "Introduction to Theory of Computation" by Michael Sipser.
I have ...
0
votes
1answer
94 views
DFA Minimization: Finding all equivalence classes of $\mathsf{R_L}$ for language $011(0+1)^*011$
How do we find all equivalence classes of $\mathsf{R_L}$ for a language?
Say I'm trying to look for all equivalent classes for the regular language $\mathsf{L}$ is $011(0+1)^*011$.
Here's an ...
5
votes
1answer
157 views
Not able to convert from NFA to DFA
I have a simple problem of making a DFA which accepts all inputs starting with double letters (aa, bb) or ending with double letters (aa, bb), given $\Sigma =\{a, b\}$ is the alphabet set of the given ...
3
votes
1answer
44 views
How to find $L_q = \emptyset$, a state that is not reachable for any given string?
In the book Introduction to Languages and the Theory of Computation, I'm reading section 2.6 on how to minimize the number of states in an FA.
I'm having trouble understanding a notation defined as ...
2
votes
3answers
71 views
How does “δ:Q×Σ→Q” read in the definition of a DFA (deterministic finite acceptor)?
How do you say $\delta\colon Q \times \Sigma \to Q$ in English? Describing what $\times$" and $\to$ mean would also help.
1
vote
1answer
37 views
design of self-loops and final states in fsm
I am learning about automata and finite state machines. Consider the following automaton, that accepts the word 'ab', does not have to be infinite, just once:
alphabet: 'a','b'
states: 1,2, 3 (3 is ...
3
votes
4answers
123 views
Are there real lexers that use NFAs directly instead of first transforming them to DFAs?
I am taking the Coursera class on compilers and in the lesson about lexers it is hinted that there is a time-space tradeoff between using non-deterministic finite automaton (NFA) and deterministic ...
-5
votes
1answer
168 views
Build an FA that accepts only the language of all word with b as second letter
Build an FA that accepts only the language of all word with B as second letter
7
votes
6answers
289 views
Can we say DFA is more efficient than NFA?
I just started reading about theory of computation. If we compare which is more powerful (in accepting strings), both are same. But what about efficiency ? DFA will be fast compared to NFA, since it ...
2
votes
2answers
190 views
How come {ww} isn't regular when {uv | |u|=|v|} is?
As we know, using the pumping lemma, we can easily prove the language $L = \{ w w \mid w \in \{a,b\}^* \}$ is not a regular language.
However, the language $L_1 = \{ w_1 w_2 \mid |w_1| = |w_2| \}$ is ...
1
vote
1answer
78 views
Testing whether the language of one automaton is a subset of another
Is there an algorithm to solve following problem?
Given two finite automata $A$ and $B$. Determine whether the language recognized by automaton $A$ is a subset of language recognized by automaton $B$ ...
1
vote
2answers
162 views
Is there a name/interest for regular languages that have a non-ambiguous ending?
The basic idea is to have one or more symbol that clearly indicate the end. For example:
Non-ambiguous:
$ab^*c$
$(a|b)c$
$ab^+c$
$ab?c$
$a(b|c)$
$c(ab)^*ccc$
$acc^*d$
...
2
votes
1answer
142 views
DFA that accepts decimal representations of a natural number divisible by 43
First, I have tried to build a DFA over the alphabet $\sum = \{0,\dots, 9\}$ that accepts all decimal representations of natural numbers divisible by 3, which is quite easy because of the digit sum. ...
4
votes
1answer
166 views
Do self-loops in DFA cause infinite languages?
A true/false question: If a DFA $M$ contains a self-loop on some state $q$, then $M$ must accept an infinite language.
The answer is "false". I've read this question, but I'm still wondering why $M$ ...
0
votes
0answers
67 views
Algorithm to convert statechart to “flat” finite state machine?
Is there a well-known algorithm for converting a statechart (or "hierarchical state machine" / "UML Statechart") to a "flat" finite state machine?
In other words, if I have a state machine with ...
1
vote
2answers
45 views
Regularity of “middles” of words from regular language
I need some help with the following problem: $L$ - regular language and i have to prove that the language $P$ = {$\alpha$| $\beta\alpha\gamma \in L$, $\beta,\gamma \in (A)^*$} is regular. In other ...
2
votes
1answer
57 views
Does this DFA have a solution?
I am trying to create a DFA that can recognize strings with alphabet $\{a,b,c\}$ where $a$ and $c$ appear even number of times and where $b$ appears odd number of times.
I am wondering that this may ...
3
votes
2answers
150 views
Proving regularity via equivalence classes
Given two regular languages $L_1$ and $L_2$, we define a new language
$$L=\{w_1w_2\mid \text{ there exist two words } x,y \text{ such that } xw_1\in L_1, w_2y\in L2\}$$
How do I show that $L$ is ...
1
vote
1answer
42 views
Finite state automata, multiple completion states?
I'm currently studying for an exam for a course where some of the material covered included finite state automata, I've completed a question and I'm not sure about my answer.
Question
...
5
votes
2answers
344 views
Intersection of DFAs
I'm constructing a deterministic finite automata (DFA) for a language of all strings defined over $\{0,1\}$ whose length is even and number of $1$s is odd. I constructed each DFA separately and then ...
1
vote
1answer
48 views
Finite State Automata for recognising consecutive characters
I'm currently working on this question as part of some homework, it has me stumped.
I'm familiar with finite state automata (FSA), I know how they work and I've read everything I can find on ...
1
vote
2answers
81 views
Language acceptance by DFA
I have some questions regarding acceptance of a language by DFA
Whether more that one dfa accept a language
Whether a dfa can accept more than one language
