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,280
questions
0
votes
1answer
27 views
Is every program is equivalent to a Push Down Automata?
so I was reading about stack-organized computer. Does a stack-organized computer implies that every program is equivalent to (and not more powerful than) a Push Down Automata?
0
votes
0answers
36 views
How specifically do I need to describe (in words) the language of a regular expression?
For the regular expression $(a^*ba^*b)^*a^*$, I want to learn how to describe it in words. I know there are an even number of $b$s but how much do I need to explain it? Do I need to explain it enough ...
2
votes
1answer
73 views
How many different languages over the unary alphabet {a} are recognized by 2-state DFAs?
I am struggling to answer the following question:
How many different languages over the unary alphabet {a} are
recognized by 2-state DFAs?
According to the textbook, the hint was to first ...
2
votes
0answers
57 views
Which of these languages is regular? The Pumping Lemma seems to show none are
I've been reviewing past paper questions for an automaton course, and came across a question which effectively asks, which of these languages is regular?
$$
\{\ 0^m1^{(m \times n)}0^n\ \colon\ m,n\ge ...
2
votes
1answer
22 views
NFA equality for automata with partial transition functions and all states accepting
Given two nondeterministic finite state automata with partial transition functions, such that all states are accepting, except for the implicit failure sink state, is it possible to decide in ...
0
votes
1answer
43 views
Generate code from automata
I am trying to figure out the process of generating code (set of instructions, implementation language specifics dont matter at this time) from an automaton.
The description of my intent is vague ...
1
vote
4answers
121 views
Does infinite length strings lead to uncountable languages?
This answer says:
We can have uncountable languages only if we allow words of infinite length.
So does that means any (finite / infinite) language or any (finite / infinite) set of languages over ...
0
votes
0answers
23 views
Is it decidable whether Turing Machine never scans any tape cell more than once when started with given string
The problem:
Is it decidable that the set of pairs $(M,w)$ such that TM $M$, started with input $w$, never scans any tape cell more than once.
How can I easily prove above to be decidable. I found ...
0
votes
1answer
45 views
Is it decidable if there exists some input such that the TM makes at least five moves?
I am reading this excerpt from Ullman's book:
I have following doubts:
(related to red underline) TM can make 5 left moves or 5 right moves. So it will need at max 11 cells. Then how it says 9?
(...
1
vote
1answer
32 views
Need help with previous “Automata / Theory Of Computation” exam question
I passed by this question in a previous exam while studying for the "Automata / Theory Of Computation" and I am struggling to find answer. I would appreciate it if someone can help me with it:
This ...
2
votes
1answer
58 views
Finding the union, subtraction, and intersection of two DFAs
I recently solved problem of finding union of two DFAs and came up with some observations. I need confirmation about them along with some other facts:
I can prepare the union, subtraction and ...
2
votes
1answer
46 views
PSPACE-completeness of DFA intersection problem
Let some deterministic finite automata be given. There is a problem of determining whether the intersection of these DFA is empty, and I want to show its PSPACE-completeness.
It seems to me that I ...
0
votes
2answers
48 views
When Turing Machine behaves like Finite state automaton
I read following:
Turing Machine with finite (fixed sized) tape is essentially Finite state automaton.
Is this fact correct? My doubt is Turing Machine can go infinite loop even on finite tape if ...
0
votes
1answer
34 views
Regular Language - Context Free Language
I know this is not a question answer posting site but for the sake of explaining my doubt I will like to post a question
Let $A$ be a $regular$ $language$ and $B$ be a $CFL$ over the alphabet
$\...
-1
votes
0answers
11 views
What will the output of q0 in MOORE Machine? [closed]
What will be output of the state q0 in the equivalent MOORE machine?
2
votes
1answer
92 views
Prove/disprove: If $𝐿_1$ is a finite language but not empty and $𝐿_2$ is NOT regular then $𝐿_1 \circ 𝐿_2$ is NOT regular
That what I have so far, but I am not sure at all.
Assume toward contradiction that $𝐿_1 \circ 𝐿_2$ is regular.
Define $\Sigma' = \{\sigma'|\sigma\in\Sigma\} $.
Define a regular substitution $\...
0
votes
0answers
26 views
Turing machine and Recursively Enumerable Language
Whether a TM accepts Recursively enumerable language. Decidable or not?
And what if the question was whether a TM accepts a RE language. Decidable or not?
According to my understanding the first ...
3
votes
2answers
51 views
Are DFAs with a unary alphabet strictly less powerful than DFAs with a binary alphabet?
Are DFAs with a unary alphabet strictly less powerful than DFAs with a binary alphabet? Is this even a meaningful question?
For example, if $\Sigma = \{\texttt{0}, \texttt{1}\}$, we can encode any ...
1
vote
2answers
69 views
Is a^mb^n where m=n^2 a CFL?
Is $a^mb^n$ where $m=n^2$ a CFL?
I have a doubt regrading this problem. Say if we pop $n$ number of $a's$ from the stack for each $b$ then it is a CFL (to be exact DCFL) right?
On the other hand I ...
4
votes
1answer
309 views
Prove that the class of CFG languages that are closed under reversal is undecidable
Note
The wording of the title may be a bit vague, but I'm not asking if CFLs are closed under reversal. Please see below.
Problem Description
Given a word $w$, define $w^{r}$ to be its reversal.
...
1
vote
0answers
18 views
Writing a non-deterministic Turing machine
I got an exercise in my college in which ive been asked to write a Non deterministic Turing Machine that accepts words of this form:
Ive manage to find some sort of solution but in a Deterministic ...
0
votes
1answer
45 views
Language to regex
Let A={a,b}.
So the question is to write regular expression such that L(r) which consists of all words.
My answer is this:
L(r)= (a+b)* a* b* (a+b)*
Is this ...
0
votes
1answer
30 views
Deterministic pushdown automaton for a given language
I am trying to make a deterministic pushdown automaton from this language but without success.
Here is the language definition:
$\ L=\{0^n 1^m a^i b^j \ /\ m,n,i,j > 0 \ and \ m+n=i+j \} $
...
1
vote
1answer
58 views
Is it decidable whether a given Turing machine moves its head more than 481 cells away from the left-end marker, on input ε?
So, while reading some problems on decidability, I came across the following resource:
https://www.isical.ac.in/~ansuman/flat2018/tm-more-undecidable.pdf
Here, on page no 12, it is written that the ...
0
votes
0answers
11 views
Push Down Automatas: Is it still an accept state if stack is not empty?
I'm currently seeing if a PDA is in an accept state give an input string. After reading the entire input tape, I am currently in the accept state.
However, in the stack, there are two items in it.
So ...
0
votes
1answer
22 views
Can nfa consume more than one letter at a time
If I have a NFA/DFA and I expect inputs of 00, 01, 10, 11 can I read input in groups of 2 binary digits at a time.
like the example shown
0
votes
0answers
7 views
Equality of Languages: Empty string and Empty set [duplicate]
I was going through this exercise of automata on IIT Bombay's site, where they have asked this question as an exercise. I have answered $none$ but the ans given is $option$ $1$.
My doubt is $φ^*$ is $...
0
votes
1answer
40 views
(0+ 11*0) + (0 +11*0)(1 +01*0)* (1 +01*0) =1*0(1 +01*0)* [closed]
I needed help with the following question which belongs to Arden's theorem as I am having a hard time solving it. Please find the question below
Prove:
$$(0+ 11^*0) + (0 +11^*0)(1 +01^*0)^* (1 +01^*...
4
votes
1answer
61 views
Can every regular expression be written as sum of products?
I was trying to prove that Parikh Image of every regular language is semi-linear. Even though it is true for CFL, but this question was about regular languages.
To prove this, I decided to proceed as ...
1
vote
1answer
46 views
Different application of Arden's theorem leads to different answers
So, I have to solve for the following set of equations
$q_1$ = $q_1$a + $q_2$b + $\epsilon$
$q_2$ = $q_1$a + $q_2$b + $q_3$a
$q_3$ = $q_2$a
There are two ways to do this.
I did this
...
2
votes
1answer
122 views
Example of two undecidable languages that cannot be reduced to each other
I want to find two undecidable languages $A$ and $B$ that $A$ cannot reduce to $B$, $B$ cannot reduce to $A$(Many-one reduce). One of my thought is to let $A$ be the halting problem, let $B$ be some ...
0
votes
0answers
23 views
Converting an NPDA to a CFG
I have a question regarding conversion of NPDA to CFG. The above picture is from my lecture slides. I dont understand why they are saying 1 can be popped while transitioning from q0 to q1. It is in ...
0
votes
0answers
23 views
Use ML to create a graph
I'm currently looking for literature/papers on machine learning techniques to create structures.
In detail, I want to generate finite automata (NFA, DFA), which are useful for student-exercises. So I ...
-3
votes
2answers
181 views
Is automata concept theorized in computer science and what would be a simple example?
I understand the terms automata or automaton to mean "self operating machine".
I can't think of any such "machine" besides maybe (if it is even a machine and even exits) cyclic universe of a big-bang-...
1
vote
2answers
101 views
Can I apply Rice's theorem to decide decidability status of these languages?
I came across these languages:
A Turing machine prints a specific letter.
A Turing machine computes the products of two numbers
I was guessing whether I can apply Rice's theorem to decide upon above ...
0
votes
0answers
21 views
Possible number of DFAs, NFAs, DPDAs, NPDAs, NDTMs and DTMs for various input parameters
I came across problem asking for possilble number of DFAs for a given number of states and alphabet. I started guessing if we can find possible number different automatas for given number of states, ...
0
votes
1answer
41 views
No nonfinal states in NFA
I know that if there are no non-final states in DFA then the language accepted is $\Sigma^*$.
What will happen if there are no non-final states in an NFA? Can we say it also accepts $\Sigma^*$? Can ...
0
votes
1answer
63 views
Turing recognizable but not Turing decidable language cannot have TM do not halt on infinitely many inputs
Sorry, I think I misunderstand the question, It should read as if $L$ is turing-recognizable but not decidable, then there exists infinitely many input that any TM will not halt on it...
0
votes
1answer
75 views
Maximum number of configurations of Turing machine after $n$ moves
I came across following question:
What are maximum number of configuration of Turing Machine after $n$ moves?
The answer given was:
$k^n$, where $k$ is a branching factor.
And that "branching ...
0
votes
0answers
15 views
How FA, PDA and TM emulate each other
I came across following points at various sources:
A one-stack Turing machine is really a DPDA.
Turing machine with two stacks can accept any recursively enumerable language (and hence is as ...
0
votes
0answers
20 views
Is the language $L$=$\{<D_1,D_2> | D_1,D_2$ are DFAs over $\{0,1\}$ and $L(D_1) \subseteq L(D_2)\}$ decidable?
I came up with an algorithm to decide this language, but not sure if it is correct?
...
0
votes
0answers
15 views
Showing different derivation trees for same string X
So I understand how to do this with there being multiple symbols in each possible production, but when it is singular, it seems to get more complicated, or I am overthinking it? Would the left-most ...
1
vote
1answer
29 views
Closure of regular languages under “inverse second half”
Theorem. Show that if $L$ is regular, then so is
$$
\varphi(L)=\left\{w \in \Sigma^{*} \mid \text {there exists an } \alpha \in \Sigma^{*} \text { with }|\alpha|=|w| \text { and } \alpha w \in L\...
1
vote
1answer
17 views
NPDA question about accepting condition
Will an NPDA accept a string that reaches a final state but does not have all its input consumed yet?
0
votes
0answers
22 views
Minimal DFA for “$n$th character from the right is $a$” [duplicate]
I am given the following regular expression, which accepts all strings over $\{a,b,c\}$ whose $n$th character from the right is $a$:
$$ (a|b|c)^*a(a|b|c)^{n-1}. $$
The exercise asks for the number ...
1
vote
1answer
42 views
What kind of language does the following DFA accept?
can anyone please describe the language this FA accepts? thank you
2
votes
1answer
49 views
Does this argument prove CFLs are not closed under union?
Context free languages are not closed under complementation. This follows from their property of non-closure under intersection:
If CFLs were closed under complementation, then they must have also ...
0
votes
1answer
28 views
Designing a PDA that keeps track of the stack size
Would it be possible/legal to design a PDA that can use the stack as a way to keep track of the number of inputs seen? (i.e the size of the stack would act as some sort of counter).
What I was ...
0
votes
0answers
41 views
Pushdown Automata for number of a less than 2 times number of b
Suppose we want to design a pushdown automata for $L=\{x \in \{a,b \}^{*}:|x|_a<2|x|_b \}$, can anyone check whether my automata works?
we have 4 states $\{q_0,q_1,q_2,q_3 \}$, three stack symbols ...
1
vote
1answer
117 views
Is Half - Palindrome subset of a context-free language context-free?
Suppose we have $L$ being a context-free language. Let $L'=\{x \in \Sigma^* | xx^R \in L \}$, is $L'$ context-free as well? I know that if $L$ is regular then $L'$ is regular as well by constructing a ...
