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,361
questions
0
votes
1answer
26 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
26 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
30 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
12 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
18 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
36 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 ...
-1
votes
0answers
28 views
What is the language generated by grammar G?
I can't find what is the language generated by the grammar which has the below productions.
$$S\to AB|\epsilon$$
$$A\to aB$$
$$B\to Sb$$
I have reduced it to $S\to aSbSb | \epsilon$. But I cannot ...
0
votes
0answers
18 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
54 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
56 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
49 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 ...
1
vote
2answers
149 views
Given regular language $L$, is $L_1 = \{ w \mid \text{each prefix of } w \text{ of odd length} \in L \}$ regular?
I was given a question and don't really know to solve it.
Given a regular language $L$, is the following language also regular?
$$L_1 = \{ w \mid \text{each prefix of } w \text{ of odd length ...
0
votes
0answers
10 views
Are DPDAs accepting on final state equivalent to DPDAs accepting on empty stack equivalent? [duplicate]
Say I have a string x that is accepted by some DPDA P that accepts empty stack. Intuitively it's seems impossible for P to accept any string x.y for any y != epsilon. The below DPDA accepts on final ...
0
votes
1answer
46 views
Same notation/terminology for union of sets and concatenation (Kleene star)?
For the union of sets we use the union operator $\cup$ (or $\bigcup$). And for a concatenation (Kleene star) we also use the union operator. The operations are different, but why the same terminology ...
1
vote
1answer
47 views
Why should an average programmer learn automata theory?
Good programming relies heavily on choosing an efficient algorithm for the task at hand and yet an average programmer hardly uses 50 pages worth of algorithms from the Cormen book in his/her career.
...
-2
votes
1answer
21 views
Minimization of automata with dead state
I am supposed to minimize the following DFA automa, which contains dead state:
But after the minimization of the automata, it stayed the same.
Is it correct?
2
votes
1answer
53 views
Two-way finite automaton: How does the automaton remember the state
I have been going through a theory of Two-way finite automatons and I did not understand the given example when there were a DFA A = (Q, Σ, δ, q1, F). the 2-DFA B = (Q ∪ Q| ∪ Q|| ∪ {q0, qN, qF}, Σ ∪ {#...
0
votes
2answers
30 views
Turing Machine state going to itself
Hey guys in a turing machine can a state go to itself by reading a letter. For example,
q2 reading a 'c' to go to itself. Is that possible?
Or does it need to read a tape alphabet, such as $ to ...
0
votes
2answers
91 views
Is a language regular
Given a regular language $L$ (so there is an automaton $A$ which recognizes $L$), I need to determine whether $ L'$ is also regular, where $L'$ is given by
$$ L' = \{ \alpha \in \Sigma^* \mid (\...
1
vote
2answers
56 views
Conversion of nfa with self-loop to one without self-loop
For every nondeterministic finite state automata that has self-loop(s), there exists an equivalent nfa that does not have any self-loop. How can we prove this statement in a general basis without the ...
0
votes
0answers
41 views
generate CFG from words that have even length and have at most two 0's
How to I generate a CFG from the language that have even length and have at most
two 0’s
L3 = {w ∈ {0, 1} ∗ | w is even length, 0<=2 }
I feel stuck on meeting the criteria of maximum two 0s
My ...
1
vote
0answers
22 views
Name of this 2D automata
Today I had a weird dream about a kind of automata. Each automaton has a finite 2D grid wrapped around like a torus, formatted as a table. Execution starts in one cell. Each step it executes whatever ...
1
vote
2answers
122 views
Given regular languages $L$, $M$. Is $K=\{uw | u,w \in \Sigma^*,(\exists v \in M) uvw \in L\}$ necessarily regular?
Question is as follows: Given regular languages $L$, $M$. Is $K=\{uw | u,w \in \Sigma^*,(\exists v \in M) uvw \in L\}$ necessarily regular?
Thank you for any input.
1
vote
1answer
55 views
Prove that a finite language is regular
I want to prove that $L(G) = \{01; 11110; 10101; 000\}$ is regular.
Is it correct if I write there exists a regular expression, which is: $(01|11110|10101|000)$?
How can I also prove it using a DFA?
0
votes
1answer
32 views
Multiple paths for a accepting string in NFA?
If a string(w) is accepted by an NFA, then corresponding to w,
can there be multiple paths each starting from the start state and ending at an accepting state?
-2
votes
1answer
33 views
PDA for parentheses language
Construct a PDA for the language described by the following CFG:
$$ S \to [S] \mid \{S\} \mid \Lambda $$
How can I develop a pushdown automaton for this language?
0
votes
1answer
40 views
PDA for $L= \{w : n_a(w)+n_b(w) = 2n_c(w)\}$
I'm pretty new to the PDA topic.
How do I construct an NPDA for the language $$L= \{w : n_a(w)+n_b(w) = 2n_c(w)\}.$$
I've tried all the possibilities, but I still somehow end up accepting all words.
1
vote
1answer
71 views
Checking whether union of two languages is regular
How to check if
$L = \{c^ka^nb^n \mid k>0 \wedge n\geqslant0\} \cup \{a, b\}^*$
is regular ,where
$L_1 = \{c^ka^nb^n \mid k > 0 \wedge n\geqslant0\}$ is clearly not regular and $L_2 = \{a, ...
1
vote
1answer
28 views
Construct regular expression that contains the substring
I need to write a regular expression for the following set of strings on Σ = {a, b, c} in which the number of b’s is even, and contains abcba as a substring.
So far, the even number of b's can be ...
1
vote
3answers
46 views
What does “Every CFL is decidable” exactly mean?
I am trying to prove the fact that every CFL is decidable, however I can't come to terms with what the statement exactly means.
I know that generation of a particular string by a given CFG is a ...
1
vote
2answers
30 views
Minimisatiom using Myhill-Nerode Theorem
I have recently studied the Myhill–Nerode theorem and while applying it to minimize these FSMs, I encountered a problem. Is it always the case that the final states should be grouped together because ...
0
votes
0answers
40 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 ...
1
vote
1answer
21 views
Path NFA-eplison to DFA conversion
Does a path (as in path graph or linear graph) NFA-epsilon have a simpler or more efficient algorithm other than the subset construction to convert to a DFA? The only simplifications I have come up ...
0
votes
1answer
24 views
PDA that accepts if there is an “a” in the second half of the string
How could I build a PDA on $Σ = \{a,b\}$ that accepts if there is an "a" in the second half of the string?
Formally the language is the following: $L = \{xy \mid x ∈ Σ^*, y ∈ Σ^*aΣ^* \land |x| ≥ |y|\}...
0
votes
0answers
25 views
Give a formal description for a deterministic TM that accepts the language:. L = {#w#w^ R#w# | w ∈ {a, b} ∗}
I feel the following approach is suitable for the question but I dont know how to give a formal proof using the Turing machine 7-tuple, where :
Q is a finite set of states
X is the tape alphabet
∑ ...
0
votes
0answers
9 views
Writing a Grammar to a Language [duplicate]
is there a general method or approach to writing grammars to a language? I do not want to describe the language I have to write a grammar to as I do not want a specific answer. I am looking for ...
0
votes
1answer
55 views
If L is regular language then each equivalence class is also regular?
L is a regular language. Let's say that E is one of L's equivalence classes - is it true/false that E is also regular?
The equivalence relation is, from Wikipedia: "Given a language L, and a pair of ...
1
vote
2answers
102 views
Over the alphabet {a,b,c,d}, how would i construct a NFA that only accepts strings that end with a letter that is already part of the string?
I've been trying to create a NFA that accepts strings that end with a letter that exists in the string. For example abcdb, cbdd, acac etc. while strings like abc aacd etc are not accepted since the ...
1
vote
0answers
101 views
Queries regarding simulation of multi-tape turing machine using single tape turing machine
I was going through the classic text "Introduction to Automata Theory, Languages, and Computation"
by Jeffrey Ullman,John Hopcroft and Rajeev Motwani, where I came across the simulation of MULTI-TAPE ...
1
vote
1answer
38 views
Languages such that DFA requires $\Omega(c^k)$ states but NFA needs only $O(k)$ states?
Given an alphabet $\Sigma$, let $c=|\Sigma|$. Can a set of languages $\{L_k\}$ be created, such that any DFA for $L_k$ has $\Omega(c^k)$ states and a NFA for $L_k$ exists with $O(k)$ states?
I'm ...
0
votes
0answers
26 views
Understanding Subset construction in following example
In going through the paper, Synthesizing Runtime Enforcer of Safety Properties Under Burst Error, https://link.springer.com/chapter/10.1007/978-3-319-40648-0_6, where the example automata considered ...
0
votes
1answer
34 views
The total length of input to a pushdown automata which accepts by empty stack is an upper bound on the number states and stack symbols
I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" (3rd Edition) by Jeffrey Ullman ,John Hopcroft, Rajeev Motwani, where I came across few statements ...
0
votes
1answer
51 views
Convertion from NFA to DFA
I have converted nfa to dfa. But when I checked with some examples, it looks like it is wrong.
...
3
votes
1answer
40 views
Equivalence of states between two “quasi-deterministic” strongly connected Büchi automata accepting the same $\omega$-language
Hope someone can point me to the right direction to solve this problem.
Premise.
I call quasi-deterministic Büchi automaton (qDBA) a Büchi automaton $B = \langle S, \Sigma, S_0, \delta, F \rangle$, ...
-1
votes
1answer
38 views
CFG for this language $\{a^k b^m c^n \mid 1 \leq k, m, n, n \leq 2k\}$ [duplicate]
I'm kinda new in this topic and I don't know how to figure out the rules to make a CFG out of this language, if anyone could give me an idea or hint so I can try to solve it knowing that, I would be ...
2
votes
1answer
106 views
Is there a difference between the equivalent automaton of a grammar and an automaton which accepts the language produced by the grammar?
I have been assigned some homework in uni, related to push-down automatons (evaluated via final state, not empty stack) and context-free grammars. I have noticed that questions related to generating ...
