Questions about mathematical devices that read an input stream symbol by symbol and use a state transition map to produce an output stream, maybe using secondary storage.
0
votes
1answer
67 views
Can we minimise regular expressions using known DFA minimisation algorithms?
Of course, converting NFA to DFA is not a problem. But what about the other direction?
My motivation is the notion of minimization regular expressions using the DFA minimization algorithm.
0
votes
0answers
37 views
Prove a bisimulation relation
I need to prove a bisimulation relation on $CA_{\tau}(N)$ (communication algebra with tau-steps) and names $N$.
It need to prove that $p!d.x||p?d.y$ is bisimular with $p!d.(x||p?d.y)+p?d.(p!d.x||y)$ ...
3
votes
3answers
120 views
In a DFA, does every state have a transition on every symbol of the alphabet?
If not, then what does it mean when for some state $q$ and some symbol $a$, $\delta(q, a)$ does not exist?
2
votes
2answers
65 views
Finite automaton design
Describe a (general) procedure that, given some finite automaton M, produces a new finite automaton M’ with: M’ rejects ε, but accepts otherwise the identical language as M does.Note that M may or ...
5
votes
1answer
58 views
Paper with proof that $L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \}$ is not Deterministic Context Free?
These lecture slides sketch a proof that $L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \}$
cannot be accepted by any Deterministic Pushdown Automaton. Unfortunately, the slides give ...
2
votes
0answers
48 views
Is there a book/survey-paper outlining language class hierarchies, closure properties, etc [migrated]
I'm currently doing some Formal Language research involving classes of languages above Regular but below Context Free. I'm looking at things like Reversal-Bounded Multicounter Machines, Single-stack ...
6
votes
1answer
87 views
Is the universe problem for one-counter automata with restricted alphabet size undecidable?
Consider the following universe problem.
The universe problem. Given a finite set $\Sigma$ for a class of languages, and an automaton accepting the language $L$, decide if $L=\Sigma^*$.
In [1], ...
1
vote
1answer
46 views
DFA: Can the set of States Q be empty by definition?
Can the set of states Q be empty by definition?
I was wondering about this question when doing exercises in the pumping lemma for finite automaton.
1
vote
1answer
83 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
1answer
49 views
What does it mean to say that a language is “effectively closed” under an operation?
I've been reading some formal language theory papers, and I've come across a term that I don't understand.
The paper will often refer to a set being "effectively closed under intersection" or other ...
2
votes
2answers
81 views
PDA for this context-free grammar
I have the following CFG $G$:
$$ \begin{align}
S &\rightarrow aAbb \mid aaBb \\
A &\rightarrow aAbb \mid \epsilon \\
B &\rightarrow aaBb \mid \epsilon \\
\end{align} $$
I have to create a ...
5
votes
2answers
70 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, ...
4
votes
3answers
124 views
Does our PC work as Turing Machine?
Does our PC work as Turing Machine? The model of a Turing Machine consists of infinite memory tape, which means infinite states. But suppose if our PC has 128 MB memory and 30GB disk it would have ...
2
votes
2answers
102 views
Designing a PDA w/o $\epsilon$-moves and $\leq 2$ states to accept an $\epsilon$-free CFL by final state
I understand that any CFL can be accepted by a PDA by final state or empty store but I have been rather stumped by this question.
The question states that the PDA has at most 2 states. Clearly 1 will ...
2
votes
1answer
46 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 ...
2
votes
1answer
43 views
Syntax of a Pushdown Automata transition function
I just learned PDAs in class today, but am having problems understanding the syntax of the transition function. Could someone please explain to me the meaning of this syntax:
$\delta(q, \lambda, S) = ...
6
votes
4answers
231 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
54 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
120 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$ ...
0
votes
1answer
63 views
How to generate a pushdown automata for accepting a language?
I have an exercise in my book to come up with a pushdown automaton accepting a language.
The exercise is to come up with a state diagram for the PDA accepting the language of all odd-length strings ...
4
votes
2answers
181 views
Can a two-stack PDA accept language $a^nb^mc^nd^m$ which is not context-free?
Can a two-stack PDA accept language $L=\{a^nb^mc^nd^m \mid n \geq m\}$, which has no context-free grammar?
I don't believe this has a context-free grammar, but please correct me if I'm wrong.
1
vote
0answers
115 views
CFG to CNF conversion steps
I could find that different texts follow different steps in the conversion of CFG to Chomsky Normal Form. I couldn't find any presumptions they made in the conversion steps. I have some questions ...
2
votes
2answers
140 views
Pumping lemma for CFG doubt
I was looking at the pumping lemma for CFG. I came across the first problem $a^nb^nc^n$ and understood the answer. Then I thought of the problem $a^nb^n$. I know that this is context free and thought ...
3
votes
3answers
114 views
Why is this true: “There are countably many Turing Machines” [duplicate]
It is said that there are uncountably many languages but only countably many Turing Machines. Could someone make this clear to me?
And this doesn't mean that the set of TM is finite, yes?
4
votes
2answers
124 views
Star free language vs. regular language
I was wondering, since $a^*$ is itself a star-free language, is there a regular language that is not a star-free language? Could you give an example?
(from wikipdia) Lawson defines star-free ...
1
vote
1answer
76 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 ...
6
votes
1answer
87 views
Is there a strictly non-deterministic one-counter language whose complement is one-counter?
Let
$A= \{L \mid L \;\text{is one-counter and \(\bar{L}\) is also one-counter} \}$
Clearly, $\text{Deterministic one-counter} \subseteq A$
Is it the case that $ A = \text{Deterministic ...
-3
votes
2answers
98 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."
0
votes
1answer
74 views
Pumping Lemma for regular languages proof doubt - Sipser Book
I was reading the proof of pumping lemma from Sipser's book. I couldn't understand certain things mentioned there.
In the second paragraph he has written, "because $r_l$ occurs among first $p+1$ ...
0
votes
1answer
43 views
Proving a language is not regular with pumping lemma
I'm having a little bit of an issue with a pumping lemma problem. I've successfully completely all my other problems but this is the last one and I'm a little confused I must say. If anyone can help ...
0
votes
1answer
49 views
Mapping reduction? Reduction?
I am studying computational theory with Sisper's textbook.
I can`t quite understand the definition of "reduction"
This problem can be reduced to ATM ... bula bula ...
What is the exact reduce ...
3
votes
2answers
331 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 ?
4
votes
2answers
47 views
Formal Language Syntax
Here is the question:
Show that $L = \{0^m1^n : m > 1, n > 1, n < m \}$ is not regular.
I am not sure what superscripts mean in this situation? Does it mean something like this:
$0^5 = ...
3
votes
4answers
160 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
159 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
48 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 ...
1
vote
1answer
118 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
87 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 ...
3
votes
2answers
103 views
Equivalence of NFA and DFA - proof by construction
I was looking at the construction proof showing the equivalence of NFA and DFA from Sipser's text. It started by taking number of states of DFA as $\mathcal{P}(Q)$, where $\mathcal{P}(Q)$ is the set ...
6
votes
3answers
186 views
Is there a efficient test for if an NFA accepts a subset of another NFA?
So, I know that testing if a regular language $R$ is a subset of regular language $S$ is decidable, since we can convert them both to DFAs, compute $S \cap \bar{R} $, then test if this language is ...
5
votes
1answer
203 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
45 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 ...
3
votes
4answers
132 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 ...
1
vote
2answers
92 views
CFG with regular expression terminals on RHS
Suppose that we expand our idea of context free grammar rules to allow regular expressions of terminals on the right hand side. For example, consider $G_1$:
$\begin{align*}
S & \rightarrow (a ...
1
vote
3answers
3k views
How can $ww = www$ hold for any word $w$?
Speaking in terms of automata and regular languages, how would it be possible for a string repeating some $w$ twice equal a string repeating that same $w$ thrice? That is, why is the language
$\qquad ...
2
votes
1answer
79 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$ ...
3
votes
2answers
125 views
Prove that the language of unary not-prime numbers satisfies the Pumping Lemma
Here is a question from Daniel I. A. Cohen's book Introduction to Computer Theory:
Consider the language:
$\quad \mathrm{PRIME}' = \{ a^n \mid n \text{ is not a prime} \} = \{ \varepsilon, ...
4
votes
1answer
177 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$ ...
1
vote
1answer
67 views
Design the transition function
I need to design a Turing Machine that accepts the (context-free) language: $L(M)=\{0^{n}1^{n+1}: n\ge1$}.
$$Q=\{q_0,q_1,q_2,q_3,q_4\} ,Σ = \{0,1\}, Γ =\{0,1,X,Y,B\}, F=\{q_4\}$$
X- processed 0
Y- ...
0
votes
0answers
82 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 ...
