Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [automata]

Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

1
vote
0answers
25 views

Closure of regular languages to $A(L)=\{zyx|x,y,z \in \{0,1\}^*, xyz \in L\}$

Given: $A(L)=\{zyx|x,y,z \in \{0,1\}^*, xyz \in L\}$ Given $L \subseteq\{0,1\}^*$, Prove/Disprove: If $L$ is regular $\implies$ $A(L)$ is regular If $L$ is context free$\implies$ $A(L)$ ...
0
votes
0answers
31 views

languages are closed under the following operations

I don't how to prove these. (a) Show that the regular languages are closed under the following operations: $$ \mathbb{DROPOUT}(L) = \{ xz \mid xyz \in L,\enspace where \enspace x,z \in \Sigma^*, y \...
-1
votes
0answers
28 views

Minimum-power automata

I need to represents the minimum power automata that recognizes $L$, the language formed by all the strings on $\Sigma = \{a, b, c\}$ starting with $a$, ending with $c$, and containing as many $b$s as ...
1
vote
1answer
22 views

Not reachable accept state in DFA

I am trying to show that every deterministic complete finite automaton that recognizes the language $a^*b+b^*$ for $\Sigma = \{a,b\}$ contains a state $q$ such that no accept state can be reached from ...
-1
votes
0answers
22 views

Proving $E_{DFA}$ decidability by running $A_{DFA}$ a finite number of times(very tricky)

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
27 views

union of non-regular language and finite language

Is the union of a non-regular language and a finite language necessarily non-regular? My suspicion is that it is, and I am yet to think of a counterexample, but am not sure how one might set out a ...
0
votes
0answers
30 views

Language to DFA

Be $F_k$ a language over $\Sigma = \{0, 1, \#\}$ of the form: $L_k = \{v\#uvw | u, v, e \in \{0, 1\}^*, |v| \leq k\}$. Show that for each k: $L_k$ is regular by constructing a DFA for $L_k$. The ...
0
votes
1answer
23 views

Pumping Lemma Confusing

Note: $\lambda $ means empty in this case. If $v\neq\lambda$, then $|v|\ge1$. But then, the 2nd condition allows $uv^0w$ where $v^0=\lambda$ and $|v|=0$??? Shouldn't the 2nd condition only allow $i\...
0
votes
1answer
19 views

Proof using Pumping Lemma

For the example proof below, how could $|v|\ge1$ when we've already set it to $v^0$ (pump $0$ times)? Reference:
1
vote
1answer
34 views

Combine 2 DFAs to produce a new DFA that accept L1 U L2

I am trying to solve a problem where i have to create a new DFA that accept $L_1 \cup L_2$ where $L_1 = \{0^{3i} 1^{3j+1} 0^{3k+2} \mid i \in \mathbb{N}, j \in \mathbb{N},k\in \mathbb{N} \}$ and $L_2 =...
0
votes
1answer
37 views

Why is this an NFA, but not an FA?

It doesn't have non-deterministic paths. Every transition is one-to-one. Accepted states are defined/guaranteed on specific inputs. Not sure why its not an FA Edit: 0.0.2
1
vote
1answer
26 views

What happens when apply reversal to the empty language? [closed]

Reversal changes start states to final states and final states to start states, and changes the direction of arrows. The empty language has no final states, so does this reversal creates something ...
1
vote
0answers
21 views

Automata|f(L) take the length of a regular language's prefix to the length of the rest

If $f$ is a function of integers, define $f(L)$ to be $$ \{w \mid \text{for some $x$, with $|x| = f(|w|)$, we have $wx$ in $L$}\}. $$ Show that if $L$ is a regular language, then so if $f(L)$, if $f$...
1
vote
1answer
52 views

How would be a formal answer for an automata geometry problem?

Let an automaton $A$ sit on point $O$ $(0,0)$ and turned to the North. That automaton can execute only any combination of three different commands in each step: Move one unit forward Turn 90 degrees ...
0
votes
0answers
13 views

Show that no Büchi Automaton with less than 3 states exists for the LTL formula $ G(p_1\rightarrow XFp_2) $

Given the LTL formula $ G(p_1\rightarrow XFp_2) $, show that there is no Büchi-automaton which recognizes the same set of $ \omega $-words $ \alpha \in (\{0,1\}^2)^\omega $ with less than three states....
2
votes
1answer
25 views

Automata|The mid 1/3 of regular language is still regular

Define $$L_{\frac{1}{3}}=\{w \in \Sigma^*\ |\ \exists x,y\in \Sigma^*,\ xwy\in L,\ |x|=|w|=|y|\}$$L is a regular language, is $L_{\frac{1}{3}}$ a regular language? I think it might be similar to the ...
0
votes
1answer
22 views

The formal language $L$ is regular iff there is a “reduced” NFA

I would appreciate some help for the following exercise: $L$ is a regular language if and only if there is a "reduced" NFA $N=\langle Q,A,\Delta, q_0,F\rangle$ with $L=L(N)$. With reduced I mean ...
0
votes
1answer
28 views

How to interpret the following DFA's language?

I'm reviewing material for a class I'm retaking before I take it again, and the teacher's homeworks are incredibly cryptic and the class notes aren't very exhaustive. I have a pretty good ...
0
votes
1answer
34 views

Finding the equivalence classes of a singleton set

Given a set L which contains only the string s = 10100, I need to find the equivalence classes [t], where t is a string that is not a prefix of s. (Σ = { 0, 1 }). I've drawn the smallest DFA ...
1
vote
1answer
35 views

FA that accepts odd 1's and ends with 101

I have been trying to come up with a FA that accepts odd 1's and ends with 101, also leading zeros are allowed. So far I have this. Problem is as you can see it fails with the string ...
1
vote
4answers
62 views

The definition of the empty string.

Here I'm having some confusion on what exactly is the empty string $\epsilon$. I'm going to list some prerequisite definitions I have surrounding the string, so please correct them as necessary. I ...
2
votes
1answer
24 views

How can we modify the proof if the alphabet in $M_1$ and the alphabet in $M_2$ are not the same? (Regular Language, Sipser)

I am reading "Introduction to the Theory of Computation 3rd Edition" by Michael Sipser. How can we modify the proof if the alphabet in $M_1$ and the alphabet in $M_2$ are not the same? We ...
2
votes
1answer
25 views

DFA construction - How to construct an automaton that contains either 0 or 1 occurrences of 010?

I can't seem to make it work. I think I managed to produce a solution when it's exactly one occurrence of 010 but not when it's at most one occurrence. Check out my automaton.
0
votes
1answer
27 views

regular language proof

Question: Prove that a finite language is a regular language. How would I go about solving this? I tried my own approach (below) but didn't get far because I don't understand how I am supposed to ...
0
votes
1answer
34 views

DFM accepting sum of ab* and ba*

I have a problem with task: Draw a diagram of the deterministic finite state machine accepting the sum of languages marked with regular expressions ab* and ba*. I resolve task: Draw a diagram of the ...
2
votes
1answer
108 views

Gcd is a Regular Language [closed]

Show that GCD = {z|z = gcd(x,y), where x, y are binary numbers} is a regular language. [Hint: There is an algorithm that deals with 0s and 1s for this problem.]
0
votes
1answer
36 views

Does the empty string share properties of both zero and $\emptyset$?

I'm confused by the use of the empty string as the author uses it below. This is a excerpt from Introduction to the Theory of Computation by Sipser. Regarding the emptystring line, is this how ...
1
vote
1answer
40 views

DFM symbol a occurs twice

Let the L language over the alphabet {a, b, c} consist exactly of all words in which the symbol a occurs at least twice. Draw a diagram of the deteminist state-finite automaton accepting L and provide ...
1
vote
0answers
31 views

Open problems in Cellular Automata field

here there is a link on Wolfram about 20 open problems of CA theory. Has anyone of them been solved or tested? I'm searching for literature.
2
votes
2answers
52 views

context free language prove or disprove

I have to prove or disprove that for every language $L$ which has the properties: for every non-prime length there is at least one word in L. for every prime length none of the words are in L. is ...
0
votes
1answer
39 views

Give a state diagram for an NFA whose language L = …

L = {w ∈ {0,1,2} *: w is a ternary representation of an integer that is a multiple of 3 but not a multiple of 9} I've written a DFA accepting multiples of 3, but I'm not sure how I should proceed. ...
0
votes
1answer
50 views

Create NFA where the second symbol of the string is the same with the last symbol

I have tried: Let $L= \{a,b,c,d, \dots, z\}$. Create NFA where the second symbol of the string is the same with the last symbol. How do I solve this? Should I do repeatedly until $z$?
1
vote
1answer
29 views

If a language and its complement are context-free, is it regular?

If both $L$ and $\overline{L}$ are context-free, is $L$ necessarily regular?
1
vote
1answer
37 views

Language of this finite state automaton?

What would be the formal definition of the language for the following Finite State Automaton?
0
votes
1answer
126 views

Design DFA to check even number of 1s using 2 states.

The alphabet is {0,1}. Zero 1s in the string should be rejected. This can be done easily using 3 states. Can this be done usinng 2 states?
1
vote
2answers
47 views

Try finding languages such that L1⊆L2⊆L3 where L1,L3∉ RE and L2∈ R [duplicate]

"RE" means "recursively enumerable" and "R" means "recursive. i am looking for the simplest solution- using a known languages such that do not demand another formal proof.
1
vote
0answers
55 views

Finding languages such that L1⊆L2⊆L3 where L1,L3∉ RE and L2∈ R [duplicate]

Finding languages such that L1⊆L2⊆L3 where L1,L3∉ RE and L2∈ R i am looking for the simplest solution- using a known languages that do not demand another formal proof.
1
vote
1answer
43 views

Finding languages such that $L_1\subset L_2\subset L_3$ where $L_1,L_3\notin$ RE and $L_2\in$ R [duplicate]

I am struggling to find such languages $L_1$, $L_2$, and $L_3$ such that $L_1\subset L_2\subset L_3$ where $L_1,L_3\notin$ RE and $L_2\in$ R. I know they exist, I need help finding them.
0
votes
1answer
61 views

Finding languages such that $L_{1} \subseteq L_{2} \subseteq L_{3}$ where $L_{1}, L_{3} \notin \mathbb{R}$, $L_{2} \in \mathbb{R}$

I am struggling to find such languages $L_{1}$, $L_{2}$, and $L_{3}$ such that $$ L_{1} \subseteq L_{2} \subseteq L_{3} $$ where $L_{1}, L_{3} \notin \mathbb{R}$ and $L_{2} \in \mathbb{R}$. I know ...
4
votes
1answer
135 views

Turing machine with read only part and finite tape

Given a Turing machine whose input part is read only , and in addition to the input part has a finite tape of length K, prove that this is equivalent to a DFA. I tried to find some bound for the ...
0
votes
0answers
242 views

Need a PDA for L={ a^n b^m c^m d^n n,m>=1 }

I am trying to desing a PDA for automata lecture.Language is L={ a^n b^m c^m d^n n,m>=1 } ...
1
vote
1answer
138 views

What is the source of formal descriptions for large uncomputable ordinals clockable by Infinite Time Turing Machines?

I can imagine the process of analyzing the computation of an ITTM at any limit stage denoted by $\alpha$ if $\alpha$ is a computable ordinal: basically, we take the description of some standard Turing ...
2
votes
2answers
94 views

Given a transition table do digraph, determine if it is DFA or NFA and build grammar

For the next transition table: $$\begin{array}{|c|c|c|c|}\hline&0&1&2\\\hline a&a&b&d\\\hline b&a&b&c\\\hline c&c&d&a\\\hline d&c&c&a\\\...
0
votes
1answer
31 views

Is $L_4$ a CFL?

Consider the following language: $$L_4 = \{a^ib^jc^kd^l : i,j,k,l \ge0 \wedge i=1 \Rightarrow j=k=l\}.$$ Prove or disprove: $L_4$ is a context-free language. To me, it looks like $L_4$ can be ...
0
votes
1answer
42 views

Prove that the grammar defines language

Given grammar G, I have to prove it defines the language of all words which are not palindromes. In other words, $w\in L(G) \Leftrightarrow w\in L $ where $L =$ {w$\in$ $\sum^*$ | w is not palindrom} ...
1
vote
1answer
35 views

how to prove that L is not context free

Given $\sum_2$ = {$\begin{bmatrix} 0 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$,$\begin{bmatrix} 1 \\ 0 \end{bmatrix}$,$\begin{bmatrix} 1 \\ 1\end{bmatrix}$} , and a language $L$ = {$...
1
vote
0answers
40 views

How to guess the end of pushdown automata by emptying the stack?

Let language $L=\{\sigma_1w_1c\sigma_2w_2c...\sigma_nw_nc\}$ where: $$ 1\le n\\ \sigma_i\in \{a,b\}\\ w_i\in \{a,b\}^+\\ \exists i:i\le|w_i| $$ and at least one condition from the two conditions ...
0
votes
1answer
54 views

Convert this grammar to language

I want to convert the following grammar to language but I am not able to think and answer. $$S \to aSa \mid bSa \mid ab \mid ba$$ It gives me a lot of choices when I tried building its derivation ...
0
votes
1answer
35 views

building a DFA from equivalence classes of $R_L$(tricky)

i've encoutered an interesting question from an old exam with no solution and i was wondering: how do you build a dfa(deterministic finite automata) from given equivalence classes? this is the ...
0
votes
0answers
41 views

finding equivalence classes of $R_L$ in automata(Nerode)

i am having trouble understanding this concept. would really appreciate your corrections so i could learn and improve. 1)$L=\left\{w\:\in \Sigma^* |\:w\:begins\:and\:ends\:with\:aa\right\}$ 2)$L=\...