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,773
questions
-3
votes
2
answers
54
views
Contradiction via pumping lemma
So this is the language that I need to prove is irregular via pumping lemma, however I am completely stuck with this and seeking some advice. The other ones I have done during my tutorial are much ...
user164540
0
votes
0
answers
32
views
1 way 2 stack and 2 way 2 stack Pushdown Accepters that accepts L={a^(n^2)|n≥1}
Using a 1 way 2 stack, and a 2 way 2 stack PDA, I want to check if the length of a an input string is strictly a perfect square number. How can I do this in both approaches?
-1
votes
0
answers
58
views
Can we give an example Context-Free Language that a DPDA can not recognize [duplicate]
Can we give an example Context-Free Language that a DPDA can not recognize. If we DPDA can not recognize can you explain why?
- 1
0
votes
1
answer
30
views
Proof that $\{0^m 1^n : 0\le m\le n^2\}$ is not a CFL
I am trying to prove by the pumping lemma that $L=\{0^m1^n:0\le m\le n^2\}$ is not a CFL. Here is what I have so far.
Suppose for contradiction that it is a CFL and let $N$ be the pumping length. ...
- 315
0
votes
1
answer
60
views
Is L={0^n 1^n ∣n≥0} context free language?
I looked through many sources which give this as an example for cfl. It also makes sense according to this:
But it fails the pumping lemma test.
Let's take n=5.
According to the Pumping Lemma, we can ...
0
votes
1
answer
52
views
Informal description of Non-deterministic TM for the language $L = \{w^n \mid w \in \{a, b\}^* \text{ and } n \geq 2\}$
From a list of practice problems for a graduate Theory of Computation course. I've done quite a few problems at this point on deterministic Turing Machines, I just don't think I have fully grasped the ...
0
votes
2
answers
70
views
How to find prefixes and suffixes for infinite languages? (Automata)
L= {abc}
prefix = {epsilon,a,ab,abc}
suffix = {epsilon,c,bc,abc}
It's easy to find suffixes and prefixes for finite Regular languages. But what will be the ...
0
votes
0
answers
23
views
If we have two TMs D1 and D2 and the languages of the TMs L(D1) != L(D2), then is this problem decidable/recognizable? [duplicate]
We know that in the case where, L(D1) = L(D2), the problem is undecidable. But what happens when the languages are not equal?
I would assume it's still undecidable, but is it recognizable? And how ...
0
votes
0
answers
33
views
What is the difference between abstract machines and automata?
What is the difference between abstract machines and automata? Looking at the respective Wikipedia pages, only automata has a rigorous (mathematical) definition – abstract machines does not. And I can'...
- 203
0
votes
0
answers
27
views
What is the minimum length word accepted by the product of these simple loop automata?
Let $A_{n} = (aa|aaa|aaaa|\dots |a^{n-2})(a^{n})^* $ where $n \geq 4$ is some natural,and $A_2 = (a^2)^*, A_3 = (a^3)^*$. Clearly every transition is thus labeled by an $a$. From now on let $A_n$ ...
- 495
-1
votes
1
answer
36
views
Write a CFG for a language of the form L_1 ={a^ib^jc^kd^m|i,j,k>=0, i +j +k> m}
I'm currently having trouble coming with context free grammar to describe this language.
My current intuition is to generate an arbitrary amount of a,b,c's on my string and then whenever the character ...
0
votes
1
answer
65
views
Is the language regular A2 = {w1w2w3 | w1, w2, w3 ϵ {0, 1}* }? How to prove?
So I think the above language is regular. I tried using pumping lemma but pumping up or down, changes the value of w1 but has no relation with w2 or w3. The resulting string after pumping will also be ...
0
votes
0
answers
46
views
After converting a CFG to a PDA, what is an example input string to the PDA?
For example, the following CFG:
S$\rightarrow$aSb|$\epsilon$
A valid string within the language described by the CFG would be, e.g., "aabb".
The converted PDA has the following form:
The ...
- 111
1
vote
1
answer
44
views
How to formally show computational equivalence or universality using encodings?
I want to formally show that a computational system $\mathcal M$ is computationally universal by showing it is computationally equivalent to some already known universal system, i.e. some UTM.
To show ...
- 11
0
votes
0
answers
49
views
How to convert a NFA to alternating finite automata AFA?
I am trying to construct an AFA from a NFA, how do I know if a state of NFA becoms existential or universal in the AFA?
- 1
0
votes
1
answer
42
views
Regular expression for binary string containing no instances of 01
In order to enumerate such a regular expression, it's clear one can break down the language into the set $s =\{00,01,10,11\}$ and it is clear that we need to enumerate some expression that avoids the ...
0
votes
0
answers
31
views
Abstract models of parallel computing?
I am looking for literature on abstract models on parallel computing. I am mainly referring to models like Alternating Turing Machine, PRAM or NC-uniform equivalence (Boolean circuits) with some ...
- 1
2
votes
0
answers
34
views
Let $∑$ be an alphabet. Is the set of all DFAs over $∑$ countable?
Let $∑$ be an alphabet. Is the set of all DFAs over $∑$ countable?
I know the set of all regular languages is countable, however, it is impossible to build an injection from the DFAs to the regular ...
- 135
4
votes
1
answer
69
views
Translating non-deterministic finite automata with counters to deterministic ones
I know there are algorithms for translating regular NFAs into their corresponding DFAs. Can these algorithms be applied to automata that employ transitions involving counters in a straightforward way, ...
- 141
0
votes
0
answers
16
views
Looking for collection of protocol state machines
I'm currently studying structural properties of network and control protocols and their relation to testing. I'm specifically interested in state machines. They would not need to cover the full ...
- 161
0
votes
0
answers
66
views
How to convert NFA with multiple start states to NFA with single start state without epsilon transition?
I can easily convert NFA with multiple start states to NFA with single start state with epsilon transition.
But I want to know how can I do so without epsilon transition
Here's my idea
Suppose s1 and ...
- 1
-4
votes
1
answer
54
views
For each of the following languages, give a regular expression over {a, b}
$\{a^{2n}b^{n+k+1}a^k ∈ \{a, b\}^∗ \mid n \ge 0, k \ge 0\}$
0
votes
2
answers
63
views
Infinite Recursion as the Intuitive Foundation for the Halting Undecidability Proof
all, I was wondering if my intuitive understanding of why the halting problem is undecidable is actually correct?
TLDR: Halting problem is undecidable because it leads to infinite recursion and never ...
- 1
0
votes
1
answer
37
views
The language of chains with twice as many $a$s as $b$s is regular?
I am trying to understand the pumping lemma and its instrumentation to show a certain language is not regular. My first attempt was the following problem:
Let $L$ be the language of all words that ...
- 181
1
vote
0
answers
31
views
What is a formal grammar equivalent to one-way stack automaton?
As the title says, is there a formal grammar characterization of the class of one-way stack languages?
- 11
0
votes
0
answers
68
views
Regular expression over $\{a, b\}$ for all words with an even number of $a$s, but without consecutive $a$s
I was given the following problem.
Problem. Give a regular expression over $\{a, b\}$ whose language is the set of all words with an even number of $a$s, but without consecutive $a$s. For example, $...
- 181
0
votes
0
answers
38
views
Finding a DFA with same language as given $\epsilon$-NFA
Consider the following automaton.
How does one find a DFA with an equivalent language using an algorithm? In particular, I was requested to use the algorithm described in the answer to this question. ...
- 181
0
votes
0
answers
29
views
Regular expression - Find the equivalence classes of Nerode theorem
Find the equivalence classes of a nerode theorem and use equivalence
classes to construct a reduced DFA for the following language:
$𝑎^+(𝑏+𝜀)𝑐^*$
The answer:
$𝜀,𝑎^+,𝑎^+𝑏𝑐^∗+𝑎^+𝑐^+,(𝑏+𝑐)Σ^...
0
votes
1
answer
140
views
nfa of the Language L={w belongs to (a,b)*/w starts with aa or ends with aa} with or being not exclusive
I have a question I need to give the NFA of the following language: L={w belongs to (a,b)*/w starts with aa or ends with aa} with or being not exclusive meaning I can have a word that starts with aa ...
- 1
0
votes
0
answers
118
views
Turing machine for unary subtraction $m-n$. If $m<n$, the machine writes "$!$" $|m-n|$ times
I am trying to program a Turing machine that performs unary subtraction, $m-n$, but if $m<n$, the machine writes the $!$ symbol on the tape $|m-n|$ times. If $m=1$ and $n=3$, the machine would only ...
- 101
2
votes
1
answer
59
views
State Machines as Functors
I'm looking for more examples of the following model of state machines:
in David Spivak's book on category theory, he gives in section 3.1.2.10 and in application 4.3.1.9, a description of a finite ...
- 23
1
vote
1
answer
20
views
Meaning/veracity of "each state has [..] or two outgoing ϵ transitions" in Thompson's construction
The dragon book lists properties of an NFA N(r) created using Thompson's construction, in particular:
Each state of N(r) other than the accepting state has either one outgoing transition on a symbol ...
0
votes
0
answers
36
views
Designing functions/programs according to automaton
Suppose I have two function that always return 1 + 1:
def one_plus_one():
return 1 + 1
and Python's eval(x) that accepts ...
- 101
1
vote
1
answer
53
views
Semi-decidability of Fullness problem for Turing Machines
Input: code $u$ of a Turing Machine working on a binary alphabet.
Question: Does $M_u$ accept all words $w \in \{0,1\}^*$.
This is of course an undecidable problem. I wonder if the problem is semi-...
- 13
0
votes
0
answers
50
views
Constructing an equivalent Pushdown Automaton
I'm working on an exercise (not relevant for evaluation) that involves constructing an equivalent nondeterministic stack machine from a given machine with epsilon-transitions. However, I'm having ...
- 125
5
votes
2
answers
371
views
Creating a deterministic finite automaton for strings of 2k ones and 3q zeros or a general language
I was requested to draw the graph of a finite state machine whose language is
$$L = \{ w \in \{0, 1\}: w \text{ has $2k$ ones and $3q$ zeros }\}$$
In other words, the number of ones must be even and ...
- 181
1
vote
1
answer
101
views
Can a pushdown automaton write more than one symbols on to stack on one reading from from input tape?
The formal definition of the pushdown automata according to Mike Sisper's book on theory of computation is as follows: . The transition function however only takes in one symbol from the stack (after ...
- 51
1
vote
1
answer
38
views
Does Sipser's _Introduction to the Theory of Computation_ cover the Chomsky hierarchy?
I saw the book suggested here.
Does Sipser's Introduction to the Theory of Computation cover the Chomsky hierarchy?
I ask since, looking through a pdf copy of the book, I found no matches with "...
- 123
0
votes
0
answers
21
views
Construct polynomial-time algorithm to decide whether there is a linear classifier containing all points in X and no points in Y [duplicate]
Consider n-dimensional linear classifiers, that is, subsets of R n that have the form {(x1, x2, . . . , xn)| a1x1 + a2x2 + · · · + anxn ≥ b} for some real numbers a1, . . . , an and b. Given as input ...
- 1
1
vote
1
answer
42
views
Simple pushdown automata question
I'm trying to derive the language it represents. However, I'm kind of new to those topics. What happens if input b is gathered once or more than one time at state q without a in the stack? It does not ...
- 67
0
votes
0
answers
26
views
Removing epsilon productions from a CFG. Which is correct?
I am learning how to remove epsilon productions and the result I am getting seems to vary from other results I find.
Beginning productions:
$$S \rightarrow bSb|Ba$$
$$B \rightarrow BdSc|S|\epsilon$$
...
- 1
1
vote
1
answer
143
views
Product Construction for DFAs with different alphabets
How would you modify the Product Construction for DFAs to find a DFA that recognises the union of two regular languages with different alphabets. I am not looking for a way of finding an NFA then ...
- 23
0
votes
0
answers
52
views
Why, in principle, can a Turing machine describe any computation or procedure?
Why is it that a Turing machine can perform all kinds of calculations and procedures?
As a test, I tried to perform a four-quadratic calculation using a Turing machine myself.
However, although I ...
- 1
0
votes
1
answer
110
views
CFG for the given language $L = \{~ a^\ell a^n b^m c^m d^n e^\ell ~|~ \ell,n,m \geq 0 \}$
I am writing this CFG to solve the problem:
$S \to ASBSC$
$A \to aAe ~|~ ε$
$B \to aBd ~|~ ε$
$C \to bcC ~|~ ε$
Is this correct or not?
- 1
-1
votes
1
answer
50
views
The book says 27 terminals but I only see 10. Where are they?
On page 103 of Mike Sisper's Introdution to Theory of Computation, it says that the grammar has 27 terminals (26 being the letters of the English Alphabet and 1 being the space character) but in the ...
- 51
1
vote
2
answers
76
views
Deterministic infinite automaton equals a normal DFA?
Assume we have a deterministic infinite automaton. $DIA = (Q, δ, q_0, F)$. Meaning there is no limit to the number of states. I want to prove or disprove that this module equals a normal DFA.
Attempt
...
- 15
0
votes
0
answers
43
views
Desgining NFA under certain constraints
I've got homework to design NFA to accept a set of strings over {a,b,c} in which each string of the language satisfies: "cac" is a substring and "cc" is not a substring and the ...
- 229
0
votes
1
answer
98
views
Designing a DFA with nth character condition for any integer n
Let n be an integer. How can I write finite automata for the language L?
L = {W∈{$0,1,2$}*| The $n_{th}$ from last letter in w is $0$}.
(Please suggest answers; not hints.)
Attempt
Using Regex, I ...
- 15
0
votes
0
answers
78
views
How to prove (L+M)* = M*.(L.M*)*
Question is to simplify (LM*)* and I couldn't figure out a way to simplify it. Since (L+M)* = M*.(L.M*)*, I guess we can say that it cannot be simplified more. So how do we prove that they are the ...
- 67
1
vote
0
answers
44
views
How to develop intuition to come up with Context Free Grammar?
So i'm taking this class automata and complexity at georgia tech and we were given practice material for our exam.
one of the question is to give context free grammar for these two languages
and the ...
- 11