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
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 ...