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,633
questions
-2
votes
1
answer
27
views
determining the relationship between two regular languages using the myhill nerode theorem
For a regular language $A$ with an alphabet $\Sigma$, define an equivalence relation for strings $x,y \in \Sigma^*$ by $x\equiv_A y\Leftrightarrow \,\forall w\in \Sigma^*, xw, yw\in A$ or $xw, yw\not\...
-2
votes
0
answers
34
views
How to convert regular expression to context free grammar (b + £)(ab)*aa(ba)*(b + £)+(a + £)(ba)*bb(ab)*(a + £) [duplicate]
Want to know CFG for this RE
any one can help me to convert RE to CFG?
Where £ is epsilon
-3
votes
0
answers
40
views
is ww : w ∈ Σ∗ not regular but context-free?
May i ask if the following language is regular, context-free but not regular, or not context-free/not regular? given by {ww : w ∈ Σ∗}
- 1
-3
votes
0
answers
35
views
The Language of All Palindromes - Is it CFL?
Regarding $L=\{ww^R~|~w\in\Sigma^*\}$ - The language of all palindromes.
Is it a CFL?
I think it is, because if we take any $\Sigma$, for example $\Sigma=\{a,b\}$, then it certainty is. CFL are closed ...
- 1
0
votes
0
answers
23
views
Considering definitions as equalities, what would happen if you continually substituted a word’s definition?
I’ve had this question for several years now but have next to no programming experience, nor good connections to anybody who does. So I decided to see if stack exchange had an answer.
The idea is to ...
1
vote
1
answer
60
views
How to convert AFA to ε-NFA / NFA / DFA?
Alternating Finite Automata is a superset of NFA while being equal in expressive power to NFAs. It is defined by 6-tuple (Q∃, Q∀, Σ, δ, Q0, F) where all outgoing transitions from Q∃ are 'or'ed and ...
0
votes
1
answer
29
views
A language that is either fully accepted by synchronised DFAs or not at all
I am trying to understand the concept of synchronised DFAs. I have a question where all the states in the DFA after reading that particular word from the alphabet will reach a particular state with ...
- 1
5
votes
3
answers
90
views
If $L$ is regular then so is $\{y \mid \exists x \, xyx \in L\}$
For a language $\mathcal{L}$ over an alphabet $\Sigma$, define
$$\mathcal{SW(L)} := \{ y ∈ Σ^∗ \mid \exists x \in Σ^* \text{ such that } xyx \in \mathcal{L}\}$$
How can I prove that if $\mathcal{L}$ ...
2
votes
2
answers
64
views
Myhill–Nerode equivalence classes for the language $b^ia^{5j}$
I have to find equivalence classes for different languages based on Myhill-Nerode. I'm struggling a little bit finding these equivalence classes; for example, the language $L=\{b^*a^n\mid n≡0\pmod5\}$ ...
- 21
-2
votes
0
answers
12
views
For given machine assume some strings and evaluate those string will be accepted or not then find out the generalized language
For given machine assume some strings and evaluate those string will be accepted or not then find out the generalized language.
0
votes
0
answers
31
views
How to show a language is not recursive, without using reductions?
I would like to show a language is in not recursive (not in the family $R$) without using a reduction from a language that is known to be non-recursive. In other words, its as if I am discovering the ...
- 153
0
votes
1
answer
31
views
When is a grammar ambiguous or When is a grammar not ambiguous?
I was looking at an example of grammar from the website: grammer example
which is as follows:
S → aB / bA
S → aS / bAA / a
B → bS / aBB / b
I believe they forgot to write: A -> a
Next, we are going ...
2
votes
4
answers
243
views
What exactly is pumping length in pumping lemma?
Pumping Lemma : For any regular language $\mathbb{L}$, there exists an integer $n$, such that for all $x\in \mathbb{L}$ with $|x|\geq n$, there exists $u, v, w \in \Sigma^*$, such that $x = uvw$, and
...
-1
votes
0
answers
38
views
proof $$ L = \{ a^ib^j : i+j\equiv 4\ (mod \ 5) \} $$ is regualr using Myhill–Nerode theorem
proof that the language
$$ L = \{ a^ib^j : i+j\equiv 4\ (mod \ 5) \} $$
is regualr using Myhill–Nerode theorem.
at the begining i thought that there are all of the reminders of 5, {0,1,2,3,4}
and ...
- 115
1
vote
0
answers
59
views
Why do PDAs always halt?
Can’t a PDA get stuck in a cycle of blank transitions?
Should the implementation detect such cycles and do something about them? That seems quite complex to consider all the edge cases.
Does the ...
- 161
1
vote
1
answer
51
views
Language generated by $S \to aAb|Sb$, $A \to aAb|ab$
Let $G = (\{A,S\}, \{a,b\}, S, P\}$ be the grammar with the following productions:
\begin{align}
& S \to aAb | Sb \\
& A \to aAb | ab
\end{align}
What is the language $L(G)$ generated by the ...
- 115
1
vote
1
answer
24
views
Converting Regular Expression to Finite Automata
I am studying "Theory of Computation" by Michael Sipser. I am studying the section where he teaches how to convert "RE to FA". He uses empty transitions for union, concat and star, ...
2
votes
2
answers
88
views
Is ε a part of alphabet or property of alphabet and NFA in FA
I am reading chapter 1 of Michael Sipser's "Theory of Computation" and in the section "Formation defination of NFA" he says the following:
3rd point of the above image is the ...
1
vote
1
answer
43
views
Converting Deterministic Finite Automata to Regular Expression
I am reading Michael Sipser's "Theory of Computation". In one of the proofs he talks about converting "DFA to Regular Expression" and he talks about "GNFAs". I understand ...
0
votes
1
answer
52
views
DFA for the language of non-empty words that are no longer than $2^6$
I was given a question in Automata that I need to prove or disprove, and I thought about this language:
$$L = \{w\in \{0, 1\}^*\mid 1\le |w| \le 2^6\}$$
Can you please help me to figure out if its ...
- 3
0
votes
1
answer
86
views
How would I show function $f(x)=4x$ is Turing computable?
How to show $f: \mathbb{N} \to\mathbb{N}$ with $f(x)=4x$ where $x$ is in the set of natural numbers $x\in\mathbb{N}$) is Turing Computable?
My guess is obviously there is a finite number of operations ...
- 121
0
votes
0
answers
19
views
What is the computational class of neural networks?
What is the relationship between formal automata and the different types of neural networks? What kind of neural network would you need to be able to parse context-sensitive languages, for instance?
- 1
2
votes
1
answer
54
views
Prove/find context free grammar is unambiguous for the language $L$
I am trying to find a grammar and prove that it is unambiguous for the language $L$, where $$L = \{ w \in \{a,b\}^+; |w|_a = |w|_b \} $$
Essentially: word $w$ contains at least one $a$ and $b$; where ...
- 23
3
votes
1
answer
38
views
Build an automaton from a given automaton to prove regularity of more complex strings
let $L$ be a regular language, and let $A=\{\Sigma, Q, q_0, F, \delta\}$ be a DFA such that $L = L(A)$.
I need to prove that $$L_p=\{xy\in\Sigma^*\mid\delta(q_0, y)=p\text{ and } \delta(p, x)\in F\}$$ ...
- 241
1
vote
1
answer
45
views
Minimal DFA produced by equivalent theorem vs Myhill nerode theorem are different. What is happening?
The problem is-:
Site 1 solves this in this way-:
https://onlinesmarttrainer.blogspot.com/2020/08/minimization-of-dfa-solved-example.html
Site 2 solves this in different way-:
https://aswaddev.github....
- 41
1
vote
1
answer
34
views
How does + symbol works in regular expression?
What's the difference between $a^*+b^*$ and $(a+b)^*$?
I was going through this question. So according to the question-:
(a+b)* generates $\in$, a,b,ab,ba,aa,ba,...
whereas a*+b* generates $\in$, ...
- 13
1
vote
1
answer
33
views
Prove that $L=\{a^n b^l : n \leq l\}$ is not regular by pumping lemma
I'm currently trying to prove that $L=\{a^n b^l : n \leq l\}$ is not regular by pumping lemma
My proof:
If we choose $w$ such that $w=a^P b^P$, then since $|xy| \leq p$, $y$ must be $a^P$, meaning it ...
- 111
-2
votes
1
answer
121
views
Halting problem. Decider “recognising itself” in the input? Part 2
This is a "revision" of this question, it contained an error I now see. In a nutshell, I was wondering if in the halting problem proof the decider $D$, after recognising its source code in ...
0
votes
1
answer
27
views
If $L$ is finite and $R$ is not regular, then $R\cup L$ is not regular
Prove/Disprove: If $L$ is finite and $R$ is not regular, then $R\cup L$ is not regular.
I think that this one is true, but I am stuck:
Since $R$ is not regular, it is infinite, so $R \cup L$ is also ...
- 5
0
votes
0
answers
39
views
How to build a DFA that recognizes a language
I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser):
Build a ...
- 17
0
votes
1
answer
32
views
Finding a context free grammar (CFG) for a non-context free language (CFL) a^n b^n c^n
It is known that the language $\{a^nb^nc^n|n\geq0\}$ is not context-free (we can prove it using the pumping lemma, as shown here: Is $a^n b^n c^n$ context-free?). Yet, this answer claims it has found ...
- 1
0
votes
1
answer
24
views
Automata Regular Language - if $L_1$ and $L_1-L_2$ is regular, than $L_1\cap L_2$ is...?
Given $L_1,L_2$ which can be any regular / non-regular languages.
Let $L_1$ and $L_1-L_2$ be regular languages.
I want to know if $L_1\cap L_2$ must be regular or not.
So, I wrote $L_1-L_2=L_1\cap L_2^...
- 5
0
votes
1
answer
40
views
Finding an algorithm that decides given 2 regular expressions $E_1$ and $E_2$ and a non-negative integer $k$, whether $|L(E_1) \backslash L(E_2)| = k$
Find an algorithm that decides, given 2 regular expressions $E_1$ and $E_2$ and a non-negative integer $k$, whether $|L(E_1) \backslash L(E_2)| = k$.
I know that regular expressions are closed under ...
- 369
0
votes
1
answer
84
views
Does computer use NFA or DFA?
I am now learning about automation and I am wondering if personal computers use NFAs or DFAs.
I believe it uses a DFA since when we are clicking on something it is in a way determined what will happen....
- 103
-1
votes
1
answer
59
views
If language $P$ is not regular, is $\{ w \in \Sigma ^* : |w| \geq 1000 \}\cup P$ regular necessarily?
Prove or refute.
Let $ L = \{ w \in \Sigma ^* :\ |w| \geq 1000 \} $. Let $ P $ be a non-regular language. Then $ L \cup P $ is regular necessarily.
I think it is true, but I don't have any idea ...
- 115
1
vote
0
answers
36
views
In how far is an automaton allowed to grow based on the length of its input?
Recently, I've written a draft article on the computational power of Petri-nets.
An understanding of Petri-nets isn't really
essential to answering this question, but I'll still note
that the ...
- 11
0
votes
0
answers
31
views
NP Completness and NP Hard
i need some help regaridng this text:
CLIQUE = { G, k | G is an undirected graph that contains a clique with k nodes }
The textbook proves that CLIQUE is NP-complete. Define the language TWO-CLIQUES ...
- 13
0
votes
1
answer
51
views
I require assistance in proving this language as not regular
I'm trying to prove that L = {$0^n1^m0^n | m,n >= 1$} in NOT regular but I am struggling with the demostration process.
I know the conditions are that:
$|y| > 0$; $'y'$ can't be empty
$|xy| <...
0
votes
2
answers
45
views
Difference between this grammar
I was reading a book and there is a part in which they use this grammar
$$
X \rightarrow xY $$
$$
Y \rightarrow yZ
$$
$$ Z \rightarrow z$$
$$ Z \rightarrow \lambda $$
and other times they use this ...
0
votes
0
answers
25
views
Lower bound for $a^kb^k$ in one-tape TM
For the language
$ L= \{a^kb^k | k \geq 0 \} $
How can i show there is no one-tape Turing Machine that can decide $L$ in less than $O(n\log n)$ time ?
- 336
0
votes
0
answers
41
views
Are regular expression a* and a.a* equal?
a* = {λ, a, aa, aaa, aaaa.....}
a.a* = a.{λ, a, aa, aaa, aaaa.....} = {a, aa, aaa, aaaa, aaaaa....}
Then these two regular expressions above should not be equivalent. Please correct me if i am wrong.
1
vote
1
answer
98
views
Let L be a CFL. Is $\{1\} ^∗ ⊆ L$ a decidable problem? Is $\{1\}^∗ = L$ a decidable problem?
I am working on some automata questions and I have encountered this problem:
Let L be a CFL.
Is $\{1\}^∗ ⊆ L$ a decidable problem?
Is $\{1\}^∗ = L$ a decidable problem?
I literally have no idea how to ...
- 11
3
votes
2
answers
159
views
How to build a deterministic finite automaton from a given one with a new definition for automaton language?
I was given a new definition for a language of an automaton.
A word is part of the automaton language if and only if the automaton finished on an accepting state and it was in an accepting state at ...
- 241
0
votes
0
answers
39
views
How to convert a null state transition in nfa to dfa
i am looking to convert regular expression 0* 1* to deterministic finite automaton (DFA)
I have tried creating the NFA for the regular expression as given in the above image,
From the regular ...
- 1
1
vote
1
answer
398
views
Regular Expression for Grammar = ({X, Y, Z}, {a, b}, X, {X → aY | bZ, Y → b | bZ, Z → a | aY})
2nd year college student here, I have trouble finding for the regular expression for that grammar, any help would help :D
Regular Language of the grammar:
X → aY → ab
X → bZ → ba
X → aY → abZ → aba
X ...
- 11
0
votes
3
answers
106
views
NFA where there are two 0s separated by a multiple of 4
I've been following Automata and Formal Languages in my college and I came across
this particular exercise.
While the solution presented seems correct, I take on Automata Tutor trying this exercise a ...
- 11
-4
votes
1
answer
95
views
Creating a PDA that accepts the following language
Using automata-lib 5.0.0 (Python library), I need help creating a Python program that simulates a PDA that only accepts the following language:
L = {a^m b^n | 0 ≤ m != n}
If you could provide any ...
- 1
1
vote
1
answer
89
views
DFA for $a+b=c$, where $a,b,c$ are input in parallel
I've faced this question in my homework, it's a bonus question so it's harder than I could do now with my current knowledge, so if anyone could help I'll be thankful.
We're given $\Sigma=\{0,1\}^3$. ...
- 313
-1
votes
1
answer
30
views
What is the language that this DFA accepts?
I've faced this question in my homework, I tried to solve it but I couldn't.
We're given a DFA:
Every time I tried to define the language, I found a word that the DFA accepts but the language I ...
- 313
2
votes
0
answers
36
views
Translating weighted regular expressions with the complement operator to weighted deterministic automata
I want to implement regexp search via translation to deterministic automata, as a toy project.
TLDR: how to combine the extended regular expressions with the weighted regular expressions, with the ...
- 83