Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

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
-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\...
user avatar
-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
user avatar
-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 ∈ Σ∗}
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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}$ ...
user avatar
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\}$ ...
user avatar
-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.
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
-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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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?
user avatar
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 ...
user avatar
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\}$$ ...
user avatar
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....
user avatar
  • 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$, ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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^...
user avatar
  • 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 ...
user avatar
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....
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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| <...
user avatar
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 ...
user avatar
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 ?
user avatar
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.
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
-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 ...
user avatar
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$. ...
user avatar
-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 ...
user avatar
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 ...
user avatar

1
2 3 4 5
33