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
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 ...
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. ...
-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 ...
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 ...
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'...
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 $\...
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?
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}...
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 ...
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 ...
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 ...
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 ...
-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.
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 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

1
2 3 4 5
35