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,418
questions
0
votes
0answers
17 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 ...
0
votes
1answer
18 views
DFA to accept a String containing even number of both A and B, but rejects empty String
I want to draw a DFA to accept a String containing even number of both A and B, but rejects the empty String(ε)
I have already drawn the DFA which accepts the above language, without rejecting the ...
-2
votes
0answers
16 views
Solve and create its pda
The set of strings in {0, 1}* whose logical OR is 1. For examples, logical OR of 11011 is 1 so it has to be in set. Create its CFG and convert into PDA
1
vote
0answers
17 views
Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular?
Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular? I do not think it is. I recently posted a question and from there I was thinking if this language is regular.
If we assume on the contrary, then there ...
-3
votes
0answers
29 views
Designing CFG that accepts words of the form $b^n a c^{n+1}$
I want to design a context-free grammar for the language
$$ L = \{ b^n a c^{n+1} \mid n>0 \}. $$
I came up with the following grammar, but it accepts strings with any number of $c$. Kindly help me ...
-3
votes
0answers
21 views
Formal Languages and Automata theory test [closed]
Can someone help to solve these two tests??
First version
-1
votes
1answer
23 views
What are the practical examples of Semidecidable problems? Is NP problem a semidecidable problem?
I am going through a Turing machine topic. I know about decidable, semi decidable, and decidable problems. But honestly speaking, I did not get any practical examples of Semidecidable problems. Can ...
-1
votes
0answers
30 views
Machine that recognizes more than countable languages - is it superturing (doing hypercomputation)?
I am reading thesis http://dspace.lu.lv/dspace/bitstream/handle/7/48857/298-71916-Dimitrijevs_Maksims_md09032.pdf?sequence=1 which says:
Abstract Turing machines can recognize countably many ...
3
votes
1answer
54 views
A language that is not context free
I working through some textbook exercises, and came across a problem that I'm struggling with.
Give a CFL $L$ such that $\{x|\forall y \in \Sigma^* \space xy \in L\}$ is not a CFL.
I've got the idea ...
0
votes
0answers
40 views
NFA recognizing strings in $\{0,1\}^*$ that have two zeros separated $4i$ characters, for some $i\geq1$
I am trying to design a nondeterministic finite automaton that recognizes the language of strings in $ \{0,1\}^{\ast}$ that have two zeros separated by a string of length 4i, for some $i \geq 1$.
Let $...
2
votes
2answers
28 views
How to we prove if a right linear language is ambiguous?
Considering the following language as an example:
$$\begin{align}
S &\rightarrow aS \mid bA \\
A &\rightarrow bA \mid aB \mid aD \mid \varepsilon \\
B &\rightarrow aB \mid \varepsilon \\
D ...
2
votes
1answer
15 views
Measuring the difficulty of a sequence-to-sequence problem using automata theory
Automata theory measures the difficulty of language recognition problems by using an automaton that can accept or reject for the given string.
However, I want to measure the difficulty of a sequence-...
0
votes
1answer
30 views
Does CSL contain an empty string or not? Is empty string accepted by LBA or not?
I am confused and got contradictory statements from various sources. It is mentioned in Page no 292, Chapter 11 A Hierarchy of Formal Languages & LBA, Peter Linz -An Introduction To Finite ...
1
vote
2answers
32 views
Why Linear bounded automata requires Nondeterministic Turing machine ? Why not Deterministic Turing machine?
Going through the topic of LBA, i.e., Linear bounded automata. I found that LBA requires the NTM with some constraints on tape. I found the same information from different sources. But I did not get ...
2
votes
3answers
42 views
How to use DFA/NFA to prove the language {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular?
I'm trying to prove the language L = {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular, but don't know how to present it in a DFA/NFA.
I'm thinking to have n+1 states in a NFA, with the start state as the ...
5
votes
2answers
1k views
What are the options of head movement for a Turing machine?
I find several contradictory definitions regarding the head movements of the Turing machine. In some places, it is only L / R. While in some other formal definition; it is L / S / R. Which one is ...
0
votes
1answer
24 views
minimum number of states in cross product of two minimum DFAs
If FA1 and FA2 are 2 DFAs with minimum number of states. I want to find cross product DFA (FA1XFA2). Will the cross product DFA obtained from 2 minimum DFAs also have minimum number of states(num of ...
0
votes
1answer
25 views
Deterministic pushdown automata for the language $L=\{ a^ib^j| i \neq 2j+1, i,j>0\}$ where $\Sigma = \{a,b\}$
Does there exist a Deterministic pushdown automata for the language $L=\{ a^ib^j| i \neq 2j+1, i,j>0\}$ where $\Sigma = \{a,b\}$
I have tried to find a pushdown automata and it turned out to be a ...
-1
votes
1answer
25 views
Proving of regular language [duplicate]
Is this regular or not
L = {w1w^R | w ∈ {0,1}*
(where for any word w ∈ {0,1})*, w^R denotes the reverse of w)
-1
votes
0answers
18 views
How to find s->ss|(s)|s(s)s|Epsilon is ambiguous or not?
I have some problem with solving the above question.How can i solve that problem by using left most derivation.
6
votes
1answer
345 views
What are the closure properties of LL(k) languages?
Suppose I have two LL languages $L_1, L_2$, both describable by LL($k$) grammars for the same $k$, and regular language $R$. Which of the following are also LL languages, and can they be described by ...
1
vote
1answer
95 views
What does “lookahead” refer to?
I keep hearing about lookahead parsers, LL parsers, LR, LALR, etc... but no clear explanation behind the etymology of this word.
What does "lookahead" refer to? How does this relate to LL, ...
1
vote
2answers
46 views
How to prove that concatenating a language A and A* is commutative?
Suppose we have a language $A$. I want to prove that $AA^*$ is commutative. I know that this expression equals $A^+$, but I'm not sure how to go about a proof yet. This is my attempt so far.
If $A$ is ...
0
votes
0answers
42 views
How to show $L = \{0^{i}1^{i^{2}}| i \ge 0\}$ is not context-free using pumping lemma
I've been struggling with this problem for quite a while now and don't really understand what to do for the pumping lemma here.
We have the language $L = \{0^{i}1^{i^{2}}| i \ge 0\}$ and we need to ...
0
votes
0answers
81 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 ...
1
vote
1answer
36 views
Expert explanation of state elimination methods [duplicate]
I'm so sorry if this question is too general, but I need to understand the general process of the "State elimination method".
In other words, what is the general idea, and what is the ...
0
votes
1answer
36 views
Is automaton not practical in real coding?
This question relates with this question and answer.
May I know why "Writing a structured program for any tangle of an automaton is possible in principle, but probably not worth the hassle (...
2
votes
1answer
54 views
Proving the L' = {w|deleting one symbol from a string in L} is regular when L is regular
I have looked up a question like this online and found this solution.
I couldn't understand what the new NFA A' looks like.
Could anyone give me an example of NFA A'?
1
vote
2answers
13 views
PDA for a language where the second part is not the reverse of the first part
I came across an exercise for constructing a PDA for the following language:
$$L = \{ncm \mid n,m\in\{a,b\}^* \text{ and } n \ne m^R\}.$$
Where $L \subseteq ({a,b,c})^*$
So $n$ and $m$ are both a ...
1
vote
1answer
77 views
How to convert a decision tree to an automaton?
From what I know,
a problem can be transformed to a yes/no answer, which can be
described by a decision tree.
Solution to a problem also can be represented by a set of strings (a language), which ...
0
votes
1answer
23 views
what are the weakest preconditions of these following statements
what is the meaning of postcondition and weakest postcondition in terms of programing and what are weakest postconditons of following statements.
...
1
vote
1answer
19 views
A regular language derived from another
This is similar to a previous question I asked, but doesn't seem aminable to the same technique. Given a regular language $A$, show the following language is regular:
$$
\{x|\exists y \; |y| = 2^{|x|} ...
0
votes
1answer
32 views
Can this language be called regular?
Recently, I was facing some problems in effectively proving the following :
Consider the alphabet Σ ={0,1,2,...,9,#}, and the language of strings of the form x#y#z, where x,y and z are strings of ...
0
votes
1answer
30 views
If one of the case obeys all rules of Pumping Lemma, can we conclude there is no contradiction?
I am studying Pumping Lemma for Context Free Languages, wherein, I am slightly confused in a question where one of the case doesnt obey all rules but another case does. What's the conclusion? Do we ...
0
votes
0answers
13 views
How to convert recursive language grammar tree into automaton for optimal parsing?
So I have a definition of a sort of grammar for a programming language. Some aspects are recursive (like nesting function definitions), other parts of it are just simple non-recursive trees.
...
0
votes
2answers
61 views
How can I efficiently construct a CFG from a language
I am new to CFG's and automata in general and I came across an exercise where I needed to construct a CFG for the language {a^m b^n | n <= m + 3}.
So m can be infinitely bigger than n but n can ...
1
vote
1answer
25 views
Construct a DFA recognizing a language $L$ that has exactly $I(L)$ states
Let $L$ be a language, and consider the following relation $\equiv_L$ on strings:
$s_1 \equiv_L s_2$ if and only if, for every string $w$, we have that $s_1w \in L \Leftrightarrow s_2w \in L$.
This is ...
1
vote
1answer
48 views
Clarification on an Hopcroft book DFA minimization example
At page 156 there is an example on how to find the distinguishable states for the following automaton:
The following table shows the distinguishable states:
By applying the given definition for ...
1
vote
1answer
81 views
Check if a NFA accepts a string of non-prime length
Given a nondeterministic finite automaton $A$, give an algorithm that checks whether the language $L(A)$ decided by $A$ contains a string whose length is a composite (i.e. not prime) number.
My ...
0
votes
1answer
55 views
How to prove $\{a^nb^na^n \mid n\geq1\}$ is not regular using pumping Lemma
Here the problem is that I’m confused how to take the pumping value $p$ is it arbitrary any value?
Also I don’t know if I should prove all $3$ conditions of the pumping lemma is false or if any one ...
0
votes
0answers
12 views
Building an enumerating machine with a Turing machine
I have a Turing machine say M with a state diagram which decides a particular language...
I wanted to build an enumerating machine for the same..
Since its decidable..
I can use the following logic
...
0
votes
1answer
52 views
What language does this deterministic finite automaton accept?
Been mulling over this one for hours, my initial thought was { w ε {a,b}* | w is empty, or ends with either ab or ba} but that's clearly wrong as neither aba nor bab are accepted by the automaton. If ...
3
votes
2answers
111 views
Proof that L^2 is regular => L is regular
I'm trying to show $L^2 \in \mathsf{REG} \implies L \in \mathsf{REG}$ with $L^2 = \{w = w_1w_2 \mid w_1, w_2 \in L\}$ but I cant seem to find a proof that feels right.
I first tryed to show $L \in \...
0
votes
0answers
65 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 ...
0
votes
1answer
75 views
Computational power of a Turing Machine with infinite states
Consider a turing machine with infinite states. This machine is identical to a regular machine. Only that number of states could be infinite.
Does this machine has more computational power than a ...
4
votes
1answer
160 views
Show $L = $ { w $\in (a,b) ^* $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$ is regular
I try to show that this language is regular:
$L = $ { w $\in \ (a,b) ^ * $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$
If I build a NFA and run on it every substring of w (skip other letters ...
2
votes
1answer
474 views
Does P = NP in Cellular Automata of Hyperbolic Spaces?
I read a few years ago in this book that NP problems are tractable in the space of cellular automata in the hyperbolic plane. What does this mean? Does P = NP ...
0
votes
1answer
60 views
Proof that $\{0|1\}^*0\{0|1\}^n$ requires at least $2^{n+1}$ states
How can you prove that any DFA accepting the language generated by the regular expression $\{0|1\}^*0\{0|1\}^n$ requires at least $2^{n+1}$ states?
I first attempted induction on $n$. But I don't ...
0
votes
1answer
73 views
In an NFA, what if there are no transitions out of an accept state but there are symbols left in the string?
Let's say I have a string 0110 and after 011 I reach an accept state (let's call the accept state "q") in an NFA. However, there is no transition mentioned in the diagram from q for the ...
0
votes
1answer
59 views
Converting PDA to CFG
I am trying to understand this example of converting PDA to CFG but I am not getting the idea quite right. I do have the general understanding of theorem that if $p,q\ \epsilon\ Q $ and $X \varepsilon\...
