Questions tagged [automata]
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.
1,478
questions
1
vote
1answer
16 views
An algorithm to check if two DFA are disjoint
What is the algorithm to check if two DFA are disjoint? I want to know if there exist any string accepted by both automata.
0
votes
0answers
11 views
NFA -> DFA subset construction worst case [duplicate]
I am wondering what generic example there is so that an NFA with n states results into a DFA with 2^n states after the conversion by the subset construction. I know there is the example by Hopcroft et ...
1
vote
0answers
22 views
How to prove existance and construct finite-state transducer between two different FSM?
For example I have 2 simple FSM. I will use regular expression for clarity.
...
-4
votes
0answers
17 views
0
votes
1answer
32 views
Is the language $\{a^n b^m \mid 2n + 3m \le 1000 \}$ regular?
We have a language $$ L = \{a^n b^m \mid 2n + 3m \le 1000 \} $$
Is this language regular?
I'm trying to disprove this using the Pumping Lemma, but it didn't work.
assume I say x = $x=a^{h}$ and $y=a^{...
1
vote
0answers
12 views
What to do with operators with the same precedence in an unambiguous grammar?
I'm trying to create an unambiguous grammar for a calculator that uses $+$, $-$, $*$, $/$ and $()$.
From watching videos and reading articles online, I understand how to create the grammar with $+$, $*...
-4
votes
0answers
41 views
How to remove epsilon production from this Context Free Grammar?
I want to remove the epsilon production from the following grammar:
S → [ S ] | SS | ε
1
vote
1answer
34 views
Given two DFA's accepting the same language, does one have to refine the other?
I have a logical question that I can't quite crack:
Given two automata accepting the same language $L$, does one have to refine the other?
In other words, if $A_1$ and $A_2$ both accept $L$, with ...
1
vote
0answers
36 views
Different PDA design processes — both valid?
This video shows how to design PDA from a CFG:
https://www.youtube.com/watch?v=ZImtQBMSW_Y
Basically, we always have 4 basic states, and one of them is a "hub" for loops that implement ...
0
votes
1answer
17 views
Decidability of directed strongly connected graphs
Consider the problem of determining if a directed graph is strongly connected.
How to phrase it as a language and prove that it's decidable.
My Thoughts :
To think of decidability given a graph I ...
-2
votes
2answers
17 views
Regular expression of an FA
If we convert an NFA to a DFA, is the regular expression of the DFA the same as the NFA?
I know the difference between an NFA and DFA and the algorithm to convert an NFA to DFA
-2
votes
2answers
48 views
Convert NFA to DFA
Is there a unique DFA for every NFA or there are more than one DFA an NFA can be converted to?
I've read the algorithm for converting NFA to DFA.
0
votes
0answers
43 views
What are the technical reasons for which the empty string is not allowed to be accepted by a Turing machine?
Below are the excerpts from the automata text by Peter Linz.
Definition 9.3
Let $M = (Q,\Sigma,\Gamma,\delta,q_0,\square,F)$ be a Turing machine. Then the language accepted by $M$ is
$$L(M) = \{ w \...
1
vote
1answer
44 views
Language of decimal encodings of cubes is not regular
Prove that the language that consists of cube numbers as strings is not regular.
I wanted to use pumping lemma but couldn't
$$0, 1, 8, 27, 64, 125, 216, \dots$$
0
votes
1answer
20 views
Write the Context free Grammar
What will be the context-free grammar of $B= A_1.A_2 $
when $A_1 = \{0^n1^n|n\geq 0\}$
$A_2 = \{1^n0^n|n \geq 0\}$
Also verify using a string.
if the Grammar for
$A_1$: $S_1 \rightarrow 0S_11 | \...
2
votes
2answers
116 views
Is the union of computable enumerable sets computably enumerable
Let $\{A_n : n \in \mathbb{N}\}$ be a collection of c.e. (computably enumerable) sets. Is $\bigcup_n A_n$ c.e.?
That is, is the union of c.e. sets c.e.? Otherwise, under what conditions will this be ...
-2
votes
0answers
36 views
NP as the set of polynomial verifier and set of decidable problem in nondeterministic polynomial time
My initial idea is to show that the equality of the sets by first proving (a) ==> P is subset of NP and secondly, (b) <== NP is subset of P?
-1
votes
1answer
53 views
Is this language a context free language?
Consider the following language, where the alphabet is $\{0, 1, 2\}$:
$B = \{0^a1^b2^c|a, b, c \geq 0 \text{ and }c = ab + 1\}$.
Is this language a context free language? Prove your answer.
I am ...
3
votes
0answers
30 views
What's the difference between a Generalized Nondeterministic Finite Automaton (GNFA) and a Generalized Transition Graph (GTG)?
I've recently come across a few articles that talk about a "Generalized Transition Graph" (GTG), but I've never heard of such a thing before. This other answer to a similar question leads me ...
1
vote
2answers
43 views
PDA accepting all words not of the form $b^na^n$
I am studying Automata theory. DFAs and NFAs seem pretty straightforward to me, but I don't quite understand how to design push-down automata for context-free languages.
If I have context-free ...
1
vote
1answer
50 views
Exclusion in a context-free language?
I am learning automata theory, and I am confused about this exercise:
Give context free grammar to create the following language where the
input alphabet is $\{a,b\}$
$L = \{w \text{ where }w\text{ ...
1
vote
1answer
34 views
Finite automaton whose alphabet is $\mathbb{N}$
Is it possible to have a finite automaton where $\Sigma = \mathbb{N}$? Why or why not?
I think it is possible to have a set of all natural numbers, however I'm not sure why.
2
votes
1answer
62 views
Is $\{\varepsilon\}$ a conventional way to mark the empty language?
I am grading an exercise in Automata and Formal Languages and see many of the students use $\{\varepsilon\}$ as the empty language. At first I thought this was an error, and I have asked the lecturer ...
1
vote
1answer
44 views
Prove/Disprove: NP is closed under “mixed” complexity
Let $\displaystyle S_{1} ,S_{2} \subseteq \{0,1\}^{*}$, we say $\displaystyle x\in S_{1}°S_{2}$ if it's of the form $\displaystyle x=x_{1} x_{2} ...x_{n}$, for $\displaystyle n$ even, such that:
$\...
3
votes
1answer
53 views
Why are regular tree languages closed under intersection, but deterministic context free languages are not closed under intersection?
I am looking for intuition here. Essentially, I understand that the set of parse trees from a context free grammar forms a regular tree language. I also understand that regular tree languages are ...
0
votes
1answer
35 views
Undecidability and Unrecognizability of Language with two Turing Machines
I've been working on undecidability proofs and I found this question in the practice problems for the textbook "An Introduction to Automata Theory." I know that we start by contradicting the ...
0
votes
0answers
40 views
Co-relating the direct algo for $\epsilon-NFA$ to $DFA$ with the chain : $\epsilon-NFA \rightarrow NFA \rightarrow DFA$
I was going through the text : Compilers: Principles, Techniques and Tools by Ullman et. al where I came across the following algorithm to convert an $\epsilon\text{-NFA}$ to $\text{DFA}$
...
-3
votes
2answers
64 views
Prove that the language Cats-Vs-Dogs is undecidable
Define Σ = {a, b, c, . . . , z} be the set of letters in the English alphabet.
Prove that the following language is undecidable:
Cats-VS-Dogs = {(M) | Either “cats” ∈ L(M) or “dogs” ∈ L(M), but not ...
0
votes
1answer
29 views
Regular set of the “does not contain” kind
Given a language $L$ and a set of strings $\Sigma^* = \{0, 1\}^*$, how can I find a regular set that expresses
$L = \{ w \in \Sigma^* \mid w$ ends with $00$ and does not contain $11\}$?
Well, the part ...
-1
votes
1answer
27 views
Regular expression for the language $\{wtw^r \mid w, t \in\{0 \cup 1\}^+\}$
What is a regular expression for the language $C=\{wtw^r \mid w, t \in \{0 \cup 1\}^+\}$?
Here $w^r$ is the reverse of $w$.
0
votes
1answer
45 views
Prove no DFA with four states can accept L={111}
Assume we have a language L={111}. Prove no DFA with four states can accept L.
Can’t a DFA with 4 states accept L?
1
vote
1answer
50 views
Finite automaton for all words whose length $n$ satisfies $\operatorname{gcd}(n,504) \geq 6$
I have been working on the following homework question, and I just can't seem to make any progress:
Construct a finite automaton having fewer than 36 states that recognizes the language $\{s \in a^* :...
0
votes
1answer
35 views
Deteremine if Language is in $R$ or $RE$
$$L =\left \{ \langle M \rangle \mid \exists x\in \Sigma^* \left(\left | x \right |\leq 10000 \wedge H(M, x\right) \right \}$$
Where $H(M, x)$ denotes whether Turing machine $M$ halts on input $x$.
My ...
-1
votes
2answers
58 views
DFA for $\{0^m1^n \mid m+n \text{ is even}\}$
How do I construct a DFA for the language $\{0^m1^n \mid m+n \text{ is even}\}$? The corresponding regular expression is
$(00)^*(11)^* + (00)^*0(11)^*1$.
2
votes
0answers
38 views
Whether there exists a probabilistic automaton satisfying $\Pr \{ x \in L\}=\frac{\Pr \{ x \in L_1\}}{\Pr \{ x \in L_1\}+\Pr \{ x \in L_2\}}$
Suppose that there are two probabilistic automata $A_1$ and $A_2$ with a same finite alphabet $\Sigma$. The languages of them are $\mathcal{L}_{1} \subseteq \Sigma^*$ and $\mathcal{L}_{2} \subseteq \...
1
vote
1answer
60 views
How to prove a language isn't necessarily regular? [duplicate]
Assuming we have a regular language $L$, how can we prove that $L'= \{ xz \mid \exists y : xyz \in L \text{ and } |x|=|y|=|z|\}$ isn't necessarily regular.
So far I can't come up with much for how to ...
1
vote
1answer
31 views
Reduce PDA for a given language
I drew a Push-down Automata, accepting the following language:
$$
\{ xcy : x,y \in (a+b)^*, \#_a(x) > \#_{bb}(y) \}.
$$
Here $\#_{bb}(y)$ counts the number of times that $bb$ appears in $y$, with ...
1
vote
1answer
47 views
Computing $(a+b)^*c^*(a+b)^* \cap (b+c)^*a^*(b+c)^*$
how can I find the regular expression for this intersection ?
I've tried to find words but it did not help too much..
$$[\; (a+b)^* c^* (a+b)^* \;] \cap [\; (c+b)^* a^* (c+b)^*\;]$$
1
vote
1answer
35 views
Intuition for irregular languages
I'm struggling in understanding how to recognize irregular languages.
I know what the meaning of irregular language but still find it hard to recognize.
Are there any tips to recognize better and to ...
1
vote
1answer
32 views
All strings in which every substring 000 appears after every 1
I found this given problem as follows:
Write a regular expression where all strings in which every substring 000 appears after every 1.
Now, I also found the answer from Illinois university study ...
0
votes
0answers
25 views
Finite automaton for $\{0^{2n} : n \ge 0 \} \cup \{(100)^m : m \ge 0\}$ [duplicate]
I have to construct an FA for the following language:
$$
\{ w_1,w_2 \in \{a,b\}^* \mid w_1 = 0^{2n}, w_2 = (100)^m, \text{ for some } n,m \in \mathbb{N} \}.
$$
Does anyone here have any experience ...
0
votes
1answer
42 views
Computing FOLLOW sets of left recursive grammar
Left recursive ambiguous expression Grammar:
$E \rightarrow E+E \mid E*E \mid (E) \mid \mathbf i\mathbf d$
I tried computing FIRST and FOLLOW sets of both left recursive grammar and after ...
0
votes
2answers
87 views
Why do register machines outperform stack machines?
Wikipedia says stack machine “designs have though been routinely outperformed by the traditional register machine systems, and have remained a niche player in the market.” Why is this?
0
votes
0answers
33 views
On the queue automaton and acceptance of this language
We have this language:
$$ L = \{𝑥𝑥^r|𝑥∈Σ^∗\} $$
We want to show that it can be accepted by QA.
consider a letter like #, before anything we push it to the queue.
using this additional letter, we ...
2
votes
1answer
58 views
this language and acceptance by queue automaton
I don't know how to prove or show that:
$ L_1 = \{xx|x \in \Sigma^\ast\} $ (that can be accepted by queue automaton)
If it would be possible, show by deterministic queue automaton, if not, by non-...
2
votes
1answer
28 views
Unique decipherability of infinite regular language
Can we design an algorithm to test if a infinite regular language is a code?
We have the S-P algorithm to determinate if a finite language is a code. But how about the infinite part of regular ...
0
votes
0answers
16 views
Check if the regular expression r made up of the single symbol alphabet Σ = {a} defines language L(r) = a* [duplicate]
I have got to write an algorithm programatically using haskell. The program takes a regular expression $r$ made up of the unary alphabet $ \Sigma = \{ a \} $ and check if the regular expression $r$ ...
1
vote
1answer
46 views
Find a linear bounded automaton that accepts the language $L = \{ a^{n!} : n \geq 0 \}$
I need to construct linear bounded automaton for the language $L = \{ a^{n!} : n \geq 0 \}$. I know how LBA functions, however, I don't have a thought how it can check the n! that to in the power of a....
1
vote
1answer
35 views
State complexity of difference of two languages
Given $A_1$ - DFA with $n$ states, $A_2$ - NFA with $m$ states (both over the same alphabet - $\Sigma$). What's the state complexity, i.e. an upper bound for the amount of states of the minimal DFA, ...
1
vote
1answer
53 views
What is the theoretical minimum number of “switches” requried to implement a Turing-complete CPU?
Where "switches" are the basic abstract building blocks for logic gates: vacuum tubes, transistors, magnetic relays, or whatever. We're not counting any switches in the RAM or tape drive ...
