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
vote
1answer
18 views
Simple property of DFAs
Do you know if this simple property of a DFA is stated as a property (or theorem) in some Automata theory book (possibly with a particular name)?
Property: Given a DFA $A = \{ Q, \Sigma, \delta, q_0, ...
1
vote
1answer
12 views
How to check if DFA is actually a correct model of the intended system?
Suppose I have modeled a deterministic finite automaton of my system. How can I check if the traces generated by this system, actually represent the model I had in mind?
For example, say I have DFA ...
0
votes
0answers
23 views
Deterministic Finite State Automata - Benefits of using DFA to typical software coding and testing [on hold]
Suppose I have modeled the behavior of my system by Deterministic Finite Automaton (DFA) A, and I need to check if it satisfies a safety condition. I have created another DFA S, which represents the ...
0
votes
0answers
10 views
Java Source Code for Constrcuting Buchi Automata from LTL formulas [on hold]
I am looking for a java implementation of constructing nondeterministic B\"uchi automata from linear temporal logic formulas.
I tested several ones, but none of them worked for me. For example:
1) ...
-2
votes
0answers
42 views
Turing Machine the undecidable language
Consider the undecidable language
$$\mathrm{ALLTM} = \{\langle M\rangle \mid M\text{ is a Turing machine with }L(M) = \Sigma^*\}.$$
Suppose you had an oracle for the halting problem (that is, you have ...
-2
votes
0answers
38 views
Theory of computation [on hold]
For two languages $L_1$ and $L_2 \in E^*$, define the right quotient of $L1$ by $L2$, denoted $L_1/L_2$, as follows: $L_1/L_2=\{ w \in E^*: \text{there exists $u \in L_2$ such that $wu \in L_1$ } \}$.
...
1
vote
1answer
46 views
Why are those very similar languages in a different complexity class?
i am having a real time understand why the following two languages are in two different complexity classes(the first is NP-Hard and the second is in P). tried to look online at various resources and ...
0
votes
0answers
28 views
is this given language in class P? [duplicate]
i was wondering:
is this language in class P?
$NONDISJOINT_{DFA}\:=\:\left\{<A,B> |\:A\:and\:B\:are\:DFAS\:and\:L\left(A\right)\:\cap L\left(b\right)\:\ne \varnothing \right\}$
explanation: a ...
0
votes
0answers
19 views
How to prove this language is not context-free language by pumping lemma? [duplicate]
Could I get help to prove that the language $\{a^i b^j c^k \mid i>j>k\ge 0\}$ is not context free language by using pumping lemma?
0
votes
0answers
36 views
prove that the language is not context free language
Prove that the language $\{a^i b^j c^k $ $|$ $i>j>k \geq 0\}$ is non context free language without using the pumping lemma.
we could use some helpful facts to solve the question:
$A$ is a ...
0
votes
1answer
45 views
Operations making non-context-free languages regular [on hold]
If $A$ is a non-context free language, is $A^*$ a regular language?
If $A$ is a non-context free language and $B$ is a regular language, is it possible that their concatenation is a regular language?
0
votes
0answers
53 views
How to find the minimum number of states of a deterministic finite automaton accepting a given language [duplicate]
Let
$L$ be a language over $\Sigma$. And $\Sigma = \{0,1\}$ is a set of input alphabets.
$L = \{ w \mid w \in \Sigma^*, \text{ where $w$ is a string with numbers of 0s divisible by 3 and number of ...
0
votes
0answers
45 views
Proving $E_{DFA}$ is decidable by running $A_{DFA}$ several times
I am trying to prove that language $E_{DFA}$ is decidable using multiple executions of $A_{DFA}$ (not using the proof in Sipser's book "Introduction to the Theory of Computation").
Can i just use ...
2
votes
1answer
367 views
Some basic questions on halt and move in Turing machines
Im trying to learn about and set up Turing Machines (TMs) the simplest ways using the simplest definite rules. I am using my previous knowledge on simple Cellular Automata to do this. I want to write ...
1
vote
1answer
42 views
Brzozowki's algorithm doesn't work for this corner case
I'm a newbee learning DFA minimization. And I found that(strangely) Brzozowki's algorithm cannot give me a minimized DFA on this example:
In this DFA, $S_0$ and $S_1$ are nondistinguishable and ...
0
votes
0answers
11 views
Howcome the string “b” is accepted by this nondeterministic finite state automata per the given solution?
Am I correct that the given solution is implying that the string with a single b, "b" is accepted by this NFSA? If so, I don't understand how "b" can end up in the accepting state.
1
vote
1answer
51 views
Pushdown Automata for words x#y where x and y are different words over {0,1} that share one similarity
I was instructed to create a pushdown automaton described in the title. Basically, the pushdown automaton accepts strings of the form $x\#y$ where $x$ and $y$ are strings of 1s and 0s such that there ...
1
vote
3answers
51 views
Is it possible to define a DFA for the language of words having exactly one double letter? [closed]
Consider the language $\{ w \in \Sigma^*~|~ w~\text{contains exactly one double letter}~\}$. For example,
$baaba$ has exactly one double letter, but $baaaba$ has two double letters.
Suggested answer ...
0
votes
0answers
53 views
proving DFA stuck
This DFA fulfills:
Define a function $diff: \{0,1\}^*\to\Bbb Z$, for $w \in\{0,1\}^*$, $diff(w)=($# of 1's in $w)- ($# of 0's in $w$).
Thus, $diff(\epsilon)=0$; $diff(0)=−1$; $diff(1)=1$.
Let $L = ...
0
votes
0answers
26 views
Turing Machine using finite control memory for distinctness problem
I am building a turing machine that recognizes the following element distinctness problem and I also need the state transition diagram for it, and I just realized after you compare the first two ...
1
vote
1answer
44 views
What is the importance of the condition “| xy | < p” in pumping lemma? [duplicate]
Let L be a language. w $\in$ L , and w could be broken in xyz.
Then if L is regular, there exists a pumping length p such that:
|y| $\gt$ 0
|xy| $\le$ p
$\forall$ i $\ge$ 0, xy$^i$z $\in$ L
I ...
0
votes
1answer
35 views
Is there a way to calculate the number of all the languages over an alphabet?
Let $\Sigma = \{ a,b,c \}$ be an alphabet.
How should I calculate the number of Languages over $\Sigma$?
0
votes
0answers
34 views
dfa subtract multiple of 3 [duplicate]
Define a function 𝑑𝑖𝑓𝑓 ∈{0,1}→ℤ so: for everything w ∈{0,1}, diff w = # of 1's in w- # of 0's in w.
Thus:
𝑑𝑖𝑓𝑓 𝜀=0;
𝑑𝑖𝑓𝑓 0=−1;
𝑑𝑖𝑓𝑓 0=−1;
Let 𝐿 = {𝑤∈ {0,1} * | 𝑑𝑖𝑓𝑓 𝑤 = 3𝑚 ...
1
vote
1answer
91 views
For any two regular languages A, B, show that {xy|x ∈ A, y ∈ B, |x| = |y|} is context-free
Basically I'm wondering if the concatenation of two equal length string is context free. I've seen multiple proofs of this online using PDAs but we aren't covering them in my automata course and my ...
1
vote
1answer
28 views
Do all DFA's containing an “accepting path containing a cycle” accept infinite languages?
So I've seen this claim being made on different questions:
Do self-loops in DFA cause infinite languages?
I'd like to find formal proof for this.
I think I should also note that an "accepting path ...
-1
votes
1answer
14 views
Decidability problem solved by an alogrithm step by step difference between Decision and decidable problem
How Decision procedure and Decidable problem are different from each other?
Both are having solutions in yes and no form. Is any else solution for both?
-1
votes
0answers
23 views
DFA and regular expression of a language? [duplicate]
A language defined over an alphabet "A" having 0's and 1's. Containing exactly two
0's, but starts and ends on 1.Regular Expression for this language? And DFA of RE?
-2
votes
1answer
11 views
Regular expressions for some languages [duplicate]
Set of strings over $\{0,1\}$ having at least two occurrence of the substring 00.
$\{a^n b^m : n ≥ 4, m ≥ 3\}$.
Set of strings over the alphabet $\{a,b,c\}$ containing at least one $a$ and one $b$.
1
vote
2answers
33 views
Why $\phi$ $\cdot$ R = $\phi$, rather than $\phi$ $\cdot$ R = R in Automata? [duplicate]
I understand that $\phi$ is a null symbol.
why concatenation of any language L with $\phi$ is $\phi$ rather than L ?
0
votes
1answer
47 views
Confused about pumping lemma, What i'm missing? [duplicate]
When I apply pumping lemma on this language:
${L=\{010^n:n\ge0\}}$ over the alphabet ${\Sigma =\{0,1\}}$ I get that it is non-regular despite the fact that it is regular.
let ${n=4}$, then $w=010000$...
10
votes
2answers
704 views
Language involving irrational number is not a CFL
I am working through a hard exercise in a textbook, and I just can't figure out how to proceed. Here is the problem. Suppose we have the language $L = \{a^ib^j: i \leq j \gamma, i\geq 0, j\geq 1\}$ ...
0
votes
0answers
27 views
Show that the following languages are equal [duplicate]
I have the following exercise:
Prove that $\{ab,aba\}^*=\{\epsilon\} \cup \{a\}\{ba,baa\}^*\{b,ba\}$.
My idea was to write the words of each of the languages in the following way,for example for the ...
7
votes
1answer
104 views
Proof of Brzozowski's algorithm for DFA minimization?
Brzozowki's algorithm is cited widely. Several questions here give examples or discuss its complexity. But I haven't been able to find a proof of correctness for the algorithm. How do we prove it ...
1
vote
1answer
17 views
In an FSA, can you have more than one transition for the same symbol from a single state?
My textbook asks:
Consider the sets of strings on $\{0,1\}$ where the 4th symbol from the right end is different
from the leftmost symbol. Construct an accepting FSA.
The answer it provides ...
5
votes
4answers
93 views
Proving non-regularity of $\{a^p \mid p \in \text{Prime} \}$ without pumping lemma
I was wondering whether it is possible to prove $\{a^p \mid p \in \text{Prime} \}$ is a non-regular language without using the pumping lemma. I'm having trouble choosing an alphabet that completes the ...
3
votes
1answer
65 views
Automaton recognizing ambiguously accepted words of another automaton
Let $A$ be a nondeterministic automaton. Let $X(A)$ the set of words for which there at least two accepting paths.
In one of the previous exam, for which no answers are available, it is required to ...
1
vote
1answer
37 views
Is this language is Context-free language or not?
Is anybody can help me please to determine is this language is Context-free language or not?
L={wvw | w,v∈{a,b,c}+}
for example:
part of the language: acbac, abcab, bbcbb
not part of the language:...
1
vote
2answers
39 views
DFA & RE from descriptive definition of given regular language
I am trying to make the DFA and RE of a regular language which is define on the alphabet = {1,0} and all the strings present in these languages have exactly one 010 substring in them.
Some strings ...
1
vote
2answers
29 views
Number of final states in a minimal DFA
Is the number of final states in a DFA at least the number of final states in its minimal DFA?
Is the answer even yes? Any help would be appreciated.
2
votes
2answers
111 views
DFA which accepts all strings starting and ending with 'aa'
I have to construct a DFA which accepts set of all strings over {a,b} which start and end with 'aa'.
I have constructed the following DFA, but it does not accept 'aa' and 'aaa'. How can I make it ...
1
vote
1answer
102 views
Counter Machine (Halting Problem)
How can we show that Halting Problem for one-counter additive machines is decidable ?
1
vote
0answers
20 views
From a given regular expresssion r , can we minimize a regular expression r' such that L(r)= L(r')? [duplicate]
Please help me out for finding the solution
0
votes
2answers
41 views
(Non) Context Free language?
In an exam question it is asked to identify if the given language is Context-Free, Non Context Free or Regular.
This is the question :
In my opinion this language is not a CFL since w doesn't belong ...
1
vote
0answers
12 views
Context free/Non Context free Language [duplicate]
Let L = { uv composed of {0,1} | |u| = |v| and u = v }
Do we agree that this language is not a Context Free Language ?
If not, why ? Can you give me a pushdown automata that recognizes it or the ...
2
votes
1answer
62 views
Initial States in Moore Machine?
I went through the rules of Moore and Mealy Machine or FA. I read that both could have one initial state and no final state.
If Moore Machine has one initial state then there is a problem for ...
2
votes
2answers
71 views
DFA of (aa+bb)(a+b)* + (a+b)*(aa+bb)?
Our class teacher gave us a descriptive definition of a language in a Quiz today and ask us to make its DFA. In the middle of quiz he also told us the Regular Expression(RE) of that language but we ...
4
votes
1answer
16 views
Don’t understanding argument on words of a certain form
In my book they use the following argument which I don’t understand :
Let $L$ be a langage such that there is $m_1, ..., m_k \in \Sigma^*$ such that $ L \subset m_1^*...m_k^*$. Now choose the ...
0
votes
0answers
28 views
Prove by Pumping Lemma that Language $L=\{a^ib^kc^k : i\geq k\geq 1\}$ isn't Context-Free
I'm new to this forum. I have some difficulties on using Pumping Lemma to prove non-CF language.
Let $L=\{a^ib^kc^k : i\geq k\geq 1\}$ and the followings are my attempt.
Proof. Suppose by ...
2
votes
2answers
48 views
Is there a way a proving a language regular/non-regular that works for every possible language?
In my theory of computing class, we've been talking about how to prove languages regular and non-regular. I've heard of methods like the pumping lemma and Kolmogorov complexity to prove languages non-...
1
vote
1answer
46 views
Why language is not regular
Taken from site "Geeks For Geeks".
The lemma: "A concatenation of pattern(regular) and a non-pattern(not-regular) is also not regular language."
example: $\left \{L={a^{n}b^{2m}|n\geq 1,m\geq 1} \...
