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.
240
questions with no upvoted or accepted answers
0
votes
0
answers
177
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
50
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
31
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
390
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
192
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
0
votes
0
answers
41
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
0
votes
0
answers
51
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
0
votes
0
answers
36
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
0
votes
0
answers
53
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
128
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
0
votes
0
answers
60
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 ...
- 275
0
votes
0
answers
88
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
0
votes
1
answer
95
views
Simplifying regex expression (L+M*)*
To simplify it, it seems that we can do $(L+M^*)^* = (L+M)^*$, but I also need to prove it.$(L+M)^* β (L+M^*)^*$ seems straight forward. However, $(L+M^*)^* β (L+M)^*$ is what I couldn't figure out. ...
- 67
0
votes
0
answers
138
views
prove that Every DPDA has an equivalent DPDA that always reads the entire input string
I am reading Michael Sipser's book Introduction to the Theory of Computation and in the section 2.4(chapter 2 and DCFLs section) there is a proof for the lemma that says "Every DPDA has an ...
- 1
0
votes
3
answers
106
views
Can we further minimize this regular expression: a*(ac* + bc* + cc* + b*bc* + b*cc* ) + b*(bc* + cc*) + c*
I am trying to create the regular expression for the automaton named "full closure" in the following diagram using the arden's theorem:
Since, we have 3 accepting states, we would find 3 ...
- 315
0
votes
1
answer
406
views
Conversion of epsilon NFA to DFA, handling epsilon transitions
I am reading Michael Sipser's "Introduction to theory of computation" 3rd edition, page 55 - 56, the topic "equivalence of DFAs and NFAs"
Case 0: Michael Sipser asks us to handle ...
- 315
0
votes
0
answers
21
views
complement of {a^lb^mc^n:n>l+m}
If we have this language $ L = \{a^mb^nc^n:m,n \in N\}$, would its complement be $\{a,b,c\}^* \setminus L = L^\complement = \{c^nb^na^m:m,n \in N\}$? This was the professor's answer, which I find ...
- 105
0
votes
0
answers
119
views
How to find the intersection of two FAs and then check if two FAs are equal?
I am still quite confused on how to properly handle in answering the intersection and equality of two FAs in terms of table form and manipulating its transformation....
- 13
0
votes
0
answers
319
views
proof that there exists a regular expression r for every NFA with only 2 states
Let L be a regular language. Then there exists a regular expression r such that L = L(r).
Proof for NFAs with only 2 states (can be generalized!), partly seen during a lecture and completed by me:
Let ...
- 89
0
votes
1
answer
74
views
How this state set of DFA was retrieved from the given NFA
I have this NFA:
1,{2, 3}
2,empty
3,{4}
4,empty
All the arrows in this NFA are epsilon-arrows.
I understand that all possible states that can be reached from each ...
0
votes
1
answer
714
views
Help with two-tape Turing Machine for $L = \{ a^{n^2} | n \ge 0 \}$ - clarification needed
I came here to ask for help with a two-tape Turing machine for the following language.
$L = \{ a^{n^2} | n \ge 0 \}$
I tried following the advice on this site: Turing machine that accepts L={an2|nβ₯1}
[...
- 177
0
votes
0
answers
133
views
Union of two context-free grammars and their productions
Is it possible to create an union of two context-free grammars? I found a PDF material from the university of Iowa where they claim that it's possible but I just don't know how. They had that for ...
- 177
0
votes
0
answers
27
views
Considering definitions as equalities, what would happen if you continually substituted a wordβs definition?
Iβve had this question for several years now but have next to no programming experience, nor good connections to anybody who does. So I decided to see if stack exchange had an answer.
The idea is to ...
- 101
0
votes
1
answer
198
views
How to build a DFA that recognizes a language
I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser):
Build a ...
- 17
0
votes
0
answers
44
views
Lower bound for $a^kb^k$ in one-tape TM
For the language
$ L= \{a^kb^k | k \geq 0 \} $
How can i show there is no one-tape Turing Machine that can decide $L$ in less than $O(n\log n)$ time ?
- 368
0
votes
0
answers
481
views
Are regular expression a* and a.a* equal?
a* = {Ξ», a, aa, aaa, aaaa.....}
a.a* = a.{Ξ», a, aa, aaa, aaaa.....} = {a, aa, aaa, aaaa, aaaaa....}
Then these two regular expressions above should not be equivalent. Please correct me if i am wrong.
0
votes
0
answers
296
views
How to convert a null state transition in nfa to dfa
i am looking to convert regular expression 0* 1* to deterministic finite automaton (DFA)
I have tried creating the NFA for the regular expression as given in the above image,
From the regular ...
- 1
0
votes
0
answers
93
views
what's the differenece between finite state automaton and finite state automata
Upon googling all I get is the definition of finite-state automaton but what's the difference between it and finite-state automata or are they the same
- 101
0
votes
0
answers
52
views
What is the standard definition of recursive automata (or state machines)?
I found this paper:
https://courses.engr.illinois.edu/cs373/fa2009/recaut.pdf
But it looks like recursion is done along an edge. I would have thought you have state machines nested inside nodes. ...
- 495
0
votes
0
answers
68
views
conversion of regular expression to automata
I've a task to specify a finite automata (of any kind) that accepts the language described by this regular expression: $a(bab)^+b^*|(ab)^*(aa)^+$
My first solution looks like this:
I would like to ...
- 31
0
votes
0
answers
217
views
Turing Machine for Check Validity of Unary Multiplication (A=B*C)
I have a lot of difficulty with the turing machines. I understand the theory well, but I need help with a lab exercise...
Design a SINGLE TAPE Turing Machine that accepts the language $a =
> b \...
- 1
0
votes
0
answers
61
views
Context Free Grammar to Chomsky Normal Form Help
I am trying to convert the following CFG to CNF:
S -> ABS | Ξ΅
A -> BSBa | a
B -> Ba | a
The finally result looks like this:
...
0
votes
0
answers
40
views
pushdown automata question
We define a new model: A "100-PDA" is a pushdown automaton with at most 100 states and with at most 100 symbols in the stack alphabet. Prove or disprove the following statement: "There ...
0
votes
0
answers
32
views
How NFA decides how to break up a string?
If we have a language K, that word w=uv, accepts.
$K= \{{w \in \{a, b ,c\}^*: \ \vert u \vert_a \ \text{is not divisible by 3}}\}$. Can we land strings like aaaa ...
- 35
0
votes
0
answers
36
views
Finding the language of a given CFG
I'm trying to find the language of the given CFG
$S \to aB \mid bA \mid a \\ A \to bAA \mid aS \\ B \to aBB \mid bS$
I understand that the productions $S \to aB, S \to bA, A \to aS$ and $B \to bS$, ...
- 7
0
votes
0
answers
147
views
Construct a PDA that recognizes $L = \{w : w \neq a^n b^n : n β₯ 0\}$
I'm trying to find the PDA of the above language. I understand that this is the complement of the language
$L_1=\{w : w=a^nb^n : n\geq0\}$
However, I can't understand the idea behind constructing the ...
- 7
0
votes
0
answers
212
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,132
0
votes
0
answers
100
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}$
...
- 1,132
0
votes
0
answers
36
views
data structure for string queries algorithm
We have a finite set of words $D$, and denote $Pref(D)$ to be the set of all prefixes from words in $D$ and $l(D)=max_{w\in{}D}|w|$ is the length of the longest word from $D$.
Problem statement:
Given:...
- 11
0
votes
0
answers
39
views
How to get a piece of the Pie? Theoretical Plate Stacking Problem
This is just a theoretical problem that I found in the wild and want to know your solution.
A stack of plates is made between you a cousin and a few others.
Every (4 to 7) many random hours the plate ...
- 1
0
votes
0
answers
144
views
Generalization of automaton - Sipser example 1.33
I am trying to construct a nfa that generalizes Example 1.33 found in the book Introduction to the Theory of Computation by Sipser, but I am quite sure
that my transition function is wrong. I'd like ...
- 3
0
votes
0
answers
75
views
what is the function of a turing machine
The main question asked me to build a certain turing machine such that given a word w over {0,1}*
the turing machine accepts all such words and ends in accept state with the tape string = the word ...
- 145
0
votes
0
answers
560
views
Is it necessary for a Push down Automaton (PDA) to have a stack?
I am given a Finite Automaton and the question is to design an Equivalent PDA for it. This is my FA:
Is this PDA correct or do I need to add a stack to it? If its right when is the stack needed?
- 101
0
votes
2
answers
150
views
Build PDA for a language with unknown input alphabet
$L_1 ,L_2$ are regular language. We form a new language $L_{12}$ as follows:
$$L_{12}=\left \{ w_1\cdot w_2\mid w_1\in L_1\land w_2\in L_2\land |w_1|=|w_2| \right \}$$
In this exercise I am not given ...
- 217
0
votes
0
answers
40
views
Nondeterministic Turing Machine for $L^*$
If $T$ is a Turing Machine that accept a language $L$, I want to define a Turing Machine $T'$ such that accepts the language $L^*$.
An approach:
$T'$ is a nondeterministic Turing Machine which has ...
- 123
0
votes
0
answers
25
views
About quasi-linear finite automata
Let M a finite state transducer define as : $M=<X,Y,S,\delta,\lambda>$
What we mean by quasi-linear finite automata?
0
votes
0
answers
67
views
About number of NFSTs
Can we proof the number of NFSTs with $n$ states : $n.2^{mpn}.2^{n}$ where $p$ is the cardinal of input alphabet and $m$ the cardinal of output alphabet.
0
votes
0
answers
93
views
Constrained (linear) NFA-epsilon to DFA conversion
Goal: convert NFA -> DFA
Overall goal: see if the intersection of 2 of these NFAs is empty.
This will be done by converting to DFAs then DFA intersection.
input NFA: multigraph between states (each ...
- 113
0
votes
0
answers
169
views
Is there a pda with maximum 3 state for every CFL?
This is the first question I'm asking here
I'm trying to understand whether we can construct a PDA with a maximum of 3 states for every possible CFL or not? if so how?
0
votes
0
answers
141
views
Minimization of DFA- one state mark or no mark?
I want to know, what if the DFA is merged states. So if my DFA starts with q0 and then have (q0,q1) state it goes to with an 'a' for example. How do I do the table filling method.
I tried to rename ...
