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.

Filter by
Sorted by
Tagged with
-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 ...
user avatar
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?
user164486's user avatar
-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?
slm cmm's user avatar
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. ...
Addem's user avatar
  • 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 ...
Aum Thakkar's user avatar
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 ...
codeing_monkey's user avatar
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 ...
Vedant Khandelwal's user avatar
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 ...
Luis Ramirez's user avatar
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'...
The Pointer's user avatar
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$ ...
Daniel Donnelly's user avatar
-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 ...
bipartite's user avatar
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 ...
Crypton99's user avatar
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 ...
There's user avatar
  • 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 ...
Yannik Eik's user avatar
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?
Lea's user avatar
  • 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 ...
bipartite's user avatar
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 ...
Eduardo's user avatar
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 ...
Kantig Shoter's user avatar
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, ...
136's user avatar
  • 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 ...
programonkey's user avatar
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 ...
Archaic's user avatar
-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\}$
user162351's user avatar
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 ...
boinka's user avatar
  • 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 ...
lafinur's user avatar
  • 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?
Hana's user avatar
  • 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, $...
lafinur's user avatar
  • 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. ...
lafinur's user avatar
  • 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: $𝜀,𝑎^+,𝑎^+𝑏𝑐^∗+𝑎^+𝑐^+,(𝑏+𝑐)Σ^...
Mostfa Mostfa's user avatar
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 ...
LK.'s user avatar
  • 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 ...
l0ner9's user avatar
  • 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 ...
NathanLiitt's user avatar
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 ...
Evgeniy Berezovsky's user avatar
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 ...
Tu Do's user avatar
  • 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-...
Stanley's user avatar
  • 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 ...
Rico1990's user avatar
  • 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 ...
lafinur's user avatar
  • 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 ...
Sbeve's user avatar
  • 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 "...
Sam's user avatar
  • 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 ...
AZ689's user avatar
  • 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 ...
mark's user avatar
  • 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$$ ...
Ethan's user avatar
  • 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 ...
revision's user avatar
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 ...
yt10's user avatar
  • 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?
Yousaf's user avatar
  • 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 ...
Sbeve's user avatar
  • 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 ...
NitayStack's user avatar
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 ...
Yarin's user avatar
  • 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 ...
NitayStack's user avatar
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 ...
mark's user avatar
  • 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 ...
SkV's user avatar
  • 11

1
2 3 4 5
36