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
1answer
40 views

Proving $\sum_{i=1}^{n-1} i(i+1) = \frac{n(n-1)(n+1)}{3}$ for integer $n\geq 2$ [closed]

Prove the following inequality: $$\sum_{i=1}^{n-1} i(i+1) = \frac{n(n-1)(n+1)}{3}$$ for all integers $n\geq 2$ I used induction: base case and I.H I did the following: Prove by mathematical ...
2
votes
1answer
28 views

Prove that L = $ \{wuv \mid w + u = v\}$ is not context free where w, u, v is interpreted as ordinary integers.

My problem is the following; Prove that L = $ \{wuv \mid w + u = v\}$ is not context free using the pumping lemma. For instance, the string 12719 ∈ L since 12 + 7 = 19, and the string $10^n20^n30^...
0
votes
0answers
6 views

Buch automata to LTL formula help

So, I'm trying to figure out how my LTL formula should look like. I already have a Buchi automata graph ready but need the LTL formula for it. I'm adding a sketch of the Buchi automata graph. Is ...
0
votes
1answer
30 views

Describing max(L) using a regular expression - proper prefix

New to automata, looking for some clearification and some guidance. I understand the concept of prefix and proper prefix, but I'm struggling with the following question: (It is translated, so forgive ...
0
votes
0answers
9 views

prove/disprove if L(B) = (̅L̅(̅A̅)̅)̅, then NFA A is actually a DFA.

im stuck in a homework question in Automata theory: Given an NFA A over finite Alphabet, let B be NFA with complement Accept states (e.g every accept state in A is not an accept state in B and vice ...
0
votes
0answers
15 views

CFG vs DFA. I have to check the intersection of CFG and DFA.

We have a contex-free grammar and deterministic finite automaton. Propose a polynomial algorithm, that checks that the intersection of the languages they specify is not empty and estimate the time of ...
0
votes
1answer
24 views

Finite State Automaton for the language over $ \{0,1\}: $ $k^{th}$ last index is $1$

For $k\geq 1$, let $L_k$ be the Language of all binary words with a $1$ at the $k^{th}$ last position, i.e. $L_k = \{w \in \{0,1\}: w = u1a_1...a_{k-1}$ for one $u \in \{0,1\}$ and $a_j \in \{0,1\}\}$....
-1
votes
1answer
30 views

DFA Universality Criteria

I was looking for definite conditions for a DFA to be universal. So far, I've mainly found this: A DFA is universal iff all its states (minimal states) are final. This does not seem enough ...
0
votes
1answer
8 views

PDA for this CFL $L=\{a^i b^j c^k, k=i*j, i,j=0,1,2…\}$

I have troubles constructing pushdown automata for the following language: $L=\{a^i b^j c^k \mid k=i*j; \quad i,j=0,1,2...\}$ .I am not interested in the automata itself, just the idea of handling the ...
1
vote
1answer
23 views

Proving a Context Free Language

I need to prove whether a Language L = $a^ib^jc^k$ ( with i = j x k ) is context Free. I am using the pumping lemma to prove that this is not a CFL. Currently I have been able to prove in the ...
0
votes
1answer
18 views

deterministic finite-state automaton for the language L = {w ∈ {0, 1} ∗ | w does not start with 01 and does not end with 10}.

So I think this is correct but wanted to get a second opinion, but wasn't sure how to test it rather than coming up with strings. Also, it seems a bit complicated, and I was wondering if there was a ...
1
vote
0answers
60 views

Classify Turing Machine as Decidable, Co-recognizable, Recognizable

Consider the language L = {: M is a TM and M visits its start state at least twice when executed on ε}. Prove L with respect to decidability, recognizability, and co-recognizability. I think the ...
0
votes
1answer
18 views

Epsilon transition in NFA to DFA conversion

I worked through this conversion and it all makes sense except for one small part. Shouldn't $(q_1q_2)$ go to $q_1$ in the DFA on input $0$, not a self loop? We have state $q_iq_2$ to begin with ...
0
votes
2answers
32 views

Can a regular language contain non regular strings?

Check this problem (1.71 from Sipser 3rd edition): Let $\sum = \{0,1\}$. Let $A =\{0^ku0^k \ | \ k \ge 1 \ and \ u \in \sum^*$}. Show that $A$ is regular. $u$ can be $\{0,00,000,...,01,011,...,1,11,...
1
vote
1answer
36 views

NFA with ε-moves.How to remove epsilon moves and do NFA [closed]

Can someone explain me how to removes ε-moves and do NFA automata.I want to know how it works for each examples.I must see wchich state i reached for ε-moves? But how to do that? There is algorithm on ...
1
vote
0answers
36 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
37 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
vote
1answer
26 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 ...
2
votes
1answer
39 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
33 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
20 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
39 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
38 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
27 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
23 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
14 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
31 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
30 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
35 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
38 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
67 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
25 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
36 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
111 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
44 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
35 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
62 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
42 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
59 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
38 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
165 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
59 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.