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,736
questions
0
votes
0
answers
13
views
How to prove (L+M)* = M*.(L.M*)*
Question is to simplify (LM*)* and I couldn't figure out a way to simplify it. Since (L+M)* = M*.(L.M*)*, I guess we can say that it cannot be simplified more. So how do we prove that they are the ...
- 55
1
vote
0
answers
21
views
How to develop intuition to come up with Context Free Grammar?
So i'm taking this class automata and complexity at georgia tech and we were given practice material for our exam.
one of the question is to give context free grammar for these two languages
and the ...
- 11
0
votes
1
answer
25
views
Simplifying regex expression (L+M*)*
To simplify it, it seems that we can do $(L+M^*)^* = (L+M)^*$, but I also need to prove it.$(L+M)^* ⊆ (L+M^*)^*$ seems straight forward. However, $(L+M^*)^* ⊆ (L+M)^*$ is what I couldn't figure out. ...
- 55
-3
votes
0
answers
41
views
Where do I report a Security Risk if the Corporation Doesn’t Want to Hear It? [closed]
How do I communicate a security risk to a social media web site that doesn’t want to hear it?
The web site allows any person to create any number of unverified profiles.
Those unverified profiles ...
2
votes
1
answer
75
views
Regex where all strings containing an even number of 0's:
Question is to construct a regex where all strings containing an even number of 0's:
By constructing DFA graphically, it is
$$(1^*+01^*0)^* $$
But it is also
$$1^*(01^*01^*)^*$$
Can we prove that they ...
- 55
0
votes
0
answers
18
views
When converting a "empty string" regular expression to finite automata, are FA with 2 states vs 1 state equivalent?
Let's say we have a regular expression, R = $ε$. If we wanted to convert this to finite automata ( NFA or DFA ) which of the following would we use?
Have 2 states: q0 ( start state ) and q1 ( accept ...
- 305
1
vote
1
answer
36
views
Regular Expression of {w : w contains an even number of 0s and exactly two 1s}
I know the answer if it was OR would be (1*01*01*)* U 0*10*10*, but with the AND I have no clue how this can be achieved. There are lot's concatenations that I can'...
- 11
2
votes
1
answer
36
views
Is the language with at least as many 0 as 1 on any prefix $\omega$ regular?
Let $L$ be the language of infinite words in $\{0,1\}^\omega$ such that any finite prefix of a word in $L$ has at least as many $0$'s as $1$'s. Is $L$ büchi recognisable?
I think that $L$ is not $\...
- 23
0
votes
0
answers
10
views
Regular Expression of {w : w contains exactly two 0s and at least two 1s} [duplicate]
I have this 1^*011^*011^* and haven't been able to think of it differently. Can you please help me see how I can get this input 0011 and 1100 correct?
- 11
0
votes
1
answer
37
views
Pushdown Automata Construction
I had an assignment in which I had to design a pushdown automata that recognizes the language ${w \in [a,b,c]^*|w }$ have the same number of "ab" and "ba".
Tried to make a pushdown ...
3
votes
3
answers
1k
views
DFA that accepts strings whose 10th symbol from the right end is 1
Problem is "Constructing a DFA accepting set of all strings whose 10th symbol from the right end is $1$ over $\{0,1\}$"
The NFA is easy
$$(0+1)^*1(0+1)^9$$
but DFA has to have minimum $2^{10}...
- 55
1
vote
2
answers
56
views
Finite state machine that accepts every word with at least one c, or different value of parity of the counts of a's and c's
few weeks ago I had an exam in automata theory course and I've been asked to write the following non-deterministic finite automata
Write a NFA which accepts the following language - the language ...
- 11
3
votes
1
answer
613
views
Can we transfer every DFA to DFAs with start state having no in edge?
The start state cannot have any "in edge" (an arrow point directly to the start state) and only out edge is possible for the start state. Other states except the start state are free of ...
-1
votes
0
answers
44
views
Intermediate DFA question- divisibility
The question is
"The set of strings such that the number of 0's is divisible by five,
and the number of 1 's is divisible by 3 over the alphabet {0,1}"
All I could do is just 0's that are ...
- 55
3
votes
0
answers
49
views
Reference request about equivalence of automata / regular expressions up-to a language
The most widely used notion of equivalence of regular expressions
$r_1$ and $r_2$, or finite state automata ${A}_1$ and ${A}_2$ resp., over an alphabet $\Sigma$, is to consider their languages: we can ...
- 8,258
4
votes
0
answers
53
views
Is the following language recognizable by a visibly pushdown automaton?
Consider the alphabet $\Sigma = \Sigma_c \cup \Sigma_i \cup \Sigma_r$ separated into call, internal, and return letters. Assume that $c \in \Sigma_c, r \in \Sigma_c$, and $a \in \Sigma_i$.
I have a ...
1
vote
1
answer
66
views
Constructing a deterministic finite automaton from a particular regular expression
This is the given question-
Construct a DFA over the alphabet {0,1} such that it accepts all strings containing
even number of 0's OR the number of 1's divisible by 3.
The very first problem I've ...
- 11
2
votes
0
answers
147
views
What extension of a finite-state machine is modeled by aliasing inputs?
Recently, I’ve been interested in the console of the Source game engine, more specifically, its alias command, which allows one command to invoke others. It may ...
- 21
-4
votes
1
answer
38
views
Describe the language accepted by the DFA
Describe the language accepted by the DFA shown above
-1
votes
0
answers
25
views
If A is nonregular, then there exists a nonregular language B such that A∩B is infinite
Please provide a short, high level proof if the above statement is True, and a counter example if the statement is false.
0
votes
1
answer
33
views
Example 7.1 correctness in Introduction to Automata Theory, Languages, and Computation
The example says that C is unreachable, but there is the production S-> aBC so C is clearly reachable. This is an error right? or am I missing something.
- 1
0
votes
1
answer
44
views
Algorithm to determine the regularity of a language
According to the answer provided by Janoma, there are several methods to determine the regularity of a language.
Theorem
Let L ⊆ Σ∗. The following conditions are equivalent:
L is generated by a ...
1
vote
1
answer
110
views
Getting an NFA with only one initial and final state without epsilon transitions
Given an NFA with more than one initial or final state, it is possible to convert it to another NFA with only one initial or final state by using epsilon transitions. To remove the epsilon transitions,...
- 115
0
votes
1
answer
29
views
Designing DFA for a language
I am working on designing a DFA with the language $a^i b^j c^k$ such that $i + j + k$ is odd
I thought along the following lines:
$i+j+k$ is odd $\Rightarrow$ two of them are even and one is odd or ...
- 131
0
votes
0
answers
33
views
prove that Every DPDA has an equivalent DPDA that always reads the entire input string
I am reading Michael Sipser's book Introduction to the Theory of Computation and in the section 2.4(chapter 2 and DCFLs section) there is a proof for the lemma that says "Every DPDA has an ...
- 1
0
votes
1
answer
20
views
if L is CF does that mean L interaction L reverse is also CF?
if L is CF does that mean L interaction L reverse is also CF? thats the whole question since CF is clsoed for reverse it makes sense but there are alot of refute out there for interactions, so I was ...
2
votes
2
answers
96
views
Proving that there is no solution to the PCP problem using induction
I'm studying for the Algorithms and Computability course. I have encountered a problem that I cannot solve and cannot find any materials to help me solve it. It's the following PCP problem:
We have ...
- 23
0
votes
0
answers
29
views
In DFA, can a state be changed after the accepted state?
If I have the input string as 00 for this diagram, will I ever go to q3 or once I reach to q2, that state would be accepted so no matter the input string, once the state is accepted, will I never be ...
-1
votes
1
answer
25
views
find the minimization of the dfa
so this is the question , I have to minimize this DFA
this is How I did it
but when I checked for answers , this is what it was,
can someone please explain to me what mistake I made? I have been ...
1
vote
0
answers
46
views
What is the formal definition of a combinational logic?
Question Background
A finite-state machine can be defined as a 5-tuple as follows (Sipser, pg. 35):
The image below (taken from the Wikipedia article on combinational logic) seems to suggest that ...
- 111
0
votes
2
answers
69
views
When applying pumping lemma to prove that a language is not regular, do we need to apply it to all decompositions of a string or just one?
We know according to the pumping lemma if a language is regular, then a string already exists and it can be separated into 3 parts ( called decompositions ), 1 string can have multiple decompositions.
...
- 305
0
votes
0
answers
25
views
When finding the complement of Deterministic Finite Automata, do we change the trap state to accept state?
If we have a langugage L which is recognized by M1 and we need to change M1 to accept complement of L, we just need to change the accept states to non accepting states and non accepting states to ...
- 305
0
votes
1
answer
43
views
PushDown automata for a^(n) b^(2n) c^(2n) d^(n)
i got this question in a theory of computation quiz "give pda for a^(n) b^(2n) c^(2n) d^(n)"
i am arguing that there is no pda for that question but our ta says that we can push 5x to the ...
0
votes
0
answers
20
views
CPU limit for bitap algorithm bitmask
We have bitap (shift OR) algorithm that searches for a substring in a text.
Bitap algorithm uses bit masks, so that it can perform bitwise operations very fast with the help of CPU.
For example:
...
- 101
0
votes
1
answer
58
views
Can we further minimize this regular expression: a*(ac* + bc* + cc* + b*bc* + b*cc* ) + b*(bc* + cc*) + c*
I am trying to create the regular expression for the automaton named "full closure" in the following diagram using the arden's theorem:
Since, we have 3 accepting states, we would find 3 ...
- 305
0
votes
0
answers
21
views
How to reduce this regular expression: a* + a*bb* + a*bb*cc* + a*cc*?
I know minimizing regular expressions is PSPACE-HARD but we can still use identities to minimize regular expression. I can tell the reduced version of this would be a* b* c* by looking at the NFA, my ...
- 305
3
votes
1
answer
503
views
When converting a epsilon NFA to NFA to DFA, how to handle the start state?
Let's say, initially we have an epsilon NFA in which the start state, say state 1, has epsilon transition to state 3
We know when converting from epsilon NFA to NFA, we apply the following formula for ...
- 305
0
votes
1
answer
172
views
Conversion of epsilon NFA to DFA, handling epsilon transitions
I am reading Michael Sipser's "Introduction to theory of computation" 3rd edition, page 55 - 56, the topic "equivalence of DFAs and NFAs"
Case 0: Michael Sipser asks us to handle ...
- 305
0
votes
2
answers
121
views
Automata: Are there algorithms to judge whether two automata are isomorphic?
When I want to judge whether two regular forms represent the same language, I have learned the next method:
create the (non-deterministic) finite-state automata which accepts the language the given ...
- 1
1
vote
1
answer
74
views
Confusion regarding "epsilon" transition in NFAs, whether taking epsilon before or after reading the input affects the final states
Let's say we have a NFA as follows:
It has 3 states, q1 - q2 - q3 and can make transition from q1 to q2 on 0 or epsilon and from q2 to q3 on 1 or epsilon
My question is do we take epsilon transition ...
- 305
0
votes
1
answer
52
views
If $L_1 \cup L_2 \in RE$ does it implicate that at least one of them is also in RE?
This was one of my exam questions and the answer is apparently no.
Can someone explain why because I don't understand.
- 11
0
votes
1
answer
108
views
Confusion regarding the intuition behind epsilon transition in NFA
I am reading Michael Sipser's "Theory of Computation" 2nd edition, chapter 1 , Topic "Non determinism" ( Section 1.2 )
Let's use this E-NFA as an example
My question is, do we ...
- 305
0
votes
1
answer
80
views
When converting from nfa to dfa, do we always ignore the trap state?
Let's say we have a NFA such as follows:
We know it's equivalent DFA is follows, after minimization:
We know that when converting from NFA to DFA, the resultant DFA would have around 2^( number of ...
- 305
0
votes
1
answer
27
views
Reduction to Diagonalization language to prove that Universal language is not REC
I am having troubles in understanding why this proof is done like that.
Why do we need to make a reduction to Ld which isn't even in RE to disprove Lu being rec?
And why does the book (Automata Theory,...
- 3
-3
votes
1
answer
85
views
what language does S->aaSbb|SS|epslion make?
I've been thinking about this for a day now,can someone help me ?
what language does S->aaSbb|SS|epslion make?
- 1
1
vote
1
answer
50
views
Is $L = \{a^{p^2}\mid p\text{ is a prime}\}$ regular?
By pumping lemma, we choose the word $w=a^{p^2}$ that the decomposing is $[a^sa^ta^{p-s-t}]^p$
such that $u=a^s,v^i=a^t,x=a^{p-s-t}$
$[a^sa^{it}a^{p-s-t}]^p=[a^{p+it-t}]^p$
We choose i=p+1,we get $ [a^...
0
votes
0
answers
40
views
$L=\{<M>|M~is~a~TM~and~L(M)=\{0^n1^n|n\ge0\}\}$
About the language $L=\{<M>|M~is~a~TM~and~L(M)=\{0^n1^n|n\ge0\}\}$
I want to determine if it is in RE / coRE or neither.
I think that I found a mapping reduction from $\overline{A_{TM}}$ to $L$, ...
- 37
1
vote
1
answer
45
views
Mapping reduction - Bit Flip
Let $L=\{<M> | M$ is a TM, $L(M)\ne \emptyset$ and $\forall x\in L(M), \overline{x} \notin L(M) \}$
While $\overline{x}$ is the bit flip of $x$.
I want to show a mapping reduction to prove that ...
- 37
0
votes
1
answer
132
views
Turing machine for square root of n - transition table
How would someone create a Turing machine that computes ceil(sqrt(n))?
n = 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
=> f(n) = 1, 2, 2, 2, 3, 3, 3, 3, 3 ....
And that I want the input tape to have n 1's in it ...
- 1
0
votes
0
answers
22
views
How are we sure choose is going to halt? question regarding a section from Elaine Rich's Automata, Computability and Complexity book?
I have a problem regarding the choose algorithm, I provide the algorithm's definition and it's use in the book,I attached a picture for the Illustration and for how the algorithm is used.
choose (x ...
- 11