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,393
questions
0
votes
1answer
35 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
31 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
11 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
39 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
18 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
18 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
30 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
26 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
58 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
44 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
41 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
49 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
11 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
51 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
108 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 ...
-1
votes
0answers
28 views
If a language has an alternate enumerator then is L a decidable language
Let L be a non trivial language above alphabet sigma and L is not empty of sigma^*
An alternate Enumerator for Language L is an enumerator that prints an infinite series of words: w1,w2,... in which:
...
0
votes
1answer
62 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
157 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
468 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
59 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
62 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
54 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\...
0
votes
1answer
60 views
Provide a polynomial time algorithm that decides whether or not the language recognized by some input DFA consists entirely of palindromes
Everything needed to know is in the question statement. I believe that the DFA has to be acyclic (meaning its language is finite), which can be checked in polynomial time. However, finding all paths ...
0
votes
1answer
97 views
Removing left factoring from Context-Free Grammar
I know that, removing left factoring is a simple task.
And i understand following procedure:
$S→aA | aB$
Becomes:
$S→aS'$
$S'→A|B$
Yet I'm running into problems with this particular grammar:
$S→AD|...
0
votes
1answer
32 views
Confusion about definition of languages accepted by Turing Machine, very basic question
I'm studying for an upcoming exam and my book gives the following definition:
Let $M$ be a Turing machine, then the accepted language $T(M)$ of $M$ is defined as $T(M) = \{x \in \Sigma^* \mid z_0 x \...
0
votes
1answer
23 views
Is it possible to form a PDA for this language?
$$L=\left \{ a^nb^m|n\leq m\leq 2n \right \}$$
Is this even context free?
I am asking because by looking at the condition, for an expression that holds:$n< m<2n$ can be written as : $a^nb^nb^c (...
0
votes
1answer
22 views
How can I combine 2 PDA's into 1
I need to form PDA for this language: {$a^nb^m|n=m \vee n=2m$}
I know the idea of building each one separately but how do I combine them into 1 PDA?
LHS: for every 'a' I push 'A' inside stack and for ...
0
votes
0answers
45 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?
0
votes
2answers
39 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|w_1\in L_1\wedge w_2\in L_2\wedge|w_1|=|w_2| \right \}$
In this exersice I am not given any ...
1
vote
1answer
36 views
DFAs are regular languages, but regular languages are closed under concatenation
I have course notes which claim the following two facts:
First, DFAs recognize exactly the regular languages.
Second, regular languages are closed under union, concatenation, and *.
Now I have as an ...
0
votes
1answer
43 views
How to define enumeration of the set of finite state machines?
I want to write a function that takes N (maximum number of states) as a parameter, enumerates all possible finite state machines up to N states, and returns random FSM with a probability in proportion ...
1
vote
1answer
44 views
Two languages such that their Kleene closures are equal
I am trying to solve the following problem:
Find languages S and T over the alphabet $\{a, b\}$ such that $ S \not\subset T $ and $ T \not\subset\ S $ ($S$ is not contained in $T$ and not equal to $T$,...
0
votes
1answer
32 views
validation of a pumping lemma proof for regular languages
I have the following regular expression:
Of course I could think of a word like $w=a^{m+2}b^{m+2}c^{2m+3}$ and continue with the proof BUT
I was just wondering, because $L$ is made up of a union of ...
0
votes
1answer
45 views
Difference between linear bound automata and a Turing machine
Can anyone give an example where a language can be rejected by linear bounded automata and accepted by a Turing machine. Is there any proof that a linear bounded automata is less powerful than a ...
0
votes
0answers
13 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 ...
-1
votes
1answer
31 views
Turing Machine construction of M=wwRw form
Construct a Turing machine for
M = {wvw| v, w ∈ {a, b}*, reversal(v) = w}.
I tried to imagine that I will have to divide the string into 3 equal parts and check if ...
1
vote
1answer
38 views
Is this push-down automaton non-deterministic, as JFLAP states?
There is a tool called JFLAP, which, among other things, can analyze push-down automata, and find non-determinism.
In this example it is detecting non-determinism in state ...
0
votes
0answers
14 views
Convert PDA by final state in to cfg
Hope you all are doing well.
I want your assistance. I have a PDA which is accepted by the final state. I need to convert it into cfg. So I want to ask, If I want to first convert this into ...
0
votes
0answers
21 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
0answers
20 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.
-1
votes
1answer
39 views
How to show that a language is regular
I know that to show that a language is not regular, you are supposed to use the pumping lemma, but I cannot figure out how can I show that a language is regular.
How would I show that the following ...
0
votes
0answers
21 views
TM for Language With a Specific Cardinality
I'm curious about how to build TM that decide and recognize languages defined by cardinality. For example, with the language $L_1$ = $\{w \in \{0,1\}^* | |w| = 1\}$ this is the language with a single ...
2
votes
1answer
64 views
When our two-state PDA constructed from CFG is non-deterministic PDA?
We can always convert our GNF-CFG/CNF-CFG to a two-state PDA but i'm wondering when our PDA is non-deterministic? i'm sure we can not make DPDA for non-Deterministic-CFL , and i suspect that same rule ...
3
votes
1answer
67 views
Finding the upper bound of states in Minimal Deterministic Finite Automata
I have a task to determine the upper bound of states in the Minimal Deterministic Finite Automata that recognizes the language: $
L(A_1) \backslash L(A_2) $, where $ A_1 $ is a Deterministic Finite ...
0
votes
0answers
51 views
Does the order of ripping off the states matter?
Do we get same regular expressions at the end regardless of the order that we take the states step by step? Can somebody prove by exemplification?
-1
votes
1answer
29 views
How to find the language and create Push down automaton if the A is continuously looping ? and will PDA accept L produced without A
Let us consider the following Context-Free Grammar
G = ({S,A,B,C,D},{a, b}, S, P)
with production rules P:
S → SSA | Bb
A → BSA
B → A | Cb
C → AD | Cb | ɛ
D → a | b | ɛ
Let L be the language ...
0
votes
2answers
22 views
PDA with more than one initial state
I'm wondering if PDAs with more than one initial states are also accepting context free languages.
If found that question on this site about NFAs and would like to know if this answer is also valid ...
