Questions about finite automata, an elementary automaton model with finite memory. It is equivalent to regular languages and the basis for many more complex models.

learn more… | top users | synonyms

0
votes
0answers
14 views

Difference between Turing machine end state and halt

Is there a difference between the end state of a Turing machine and the halt state? Especially, for example the Busy Beaver 3. It is said that it is with 3 states but there is also a halt. Is the end ...
0
votes
2answers
31 views

How does an NFA use epsilon transitions?

In the picture I've provided, I'm trying to figure out what exactly this NFA is accepting. What's confusing me is the epsilon jump at q0. If a 0 is entered, does the system move to both q0 AND ...
1
vote
2answers
27 views

Is this language regular [duplicate]

Let L is a regular language then is L' = {x$_2$x$_1$| x$_1$x$_2$ ∈ L} regular? Thus x$_1$x$_2$ is essentially concatenation of two strings, but can reverse concatenation of same two strings yield ...
0
votes
1answer
39 views

Getting minimum DFA for regular expression (11)*+(111)*

(sorry beforehand I know putting scanned diagrams may seem not-so-professional but this problem is sticking for long and its interesting too) The language corresponding to given regex seems to ...
1
vote
1answer
40 views

Is it Regular Language?

According to Wikipedia, Regular Language is Recognized by Some DFAs, or expressed by Regular Expression .. and all finite Language are regular but, not all regular is finite .. that's mean it may be ...
-2
votes
0answers
34 views

Need help with finite automata? [on hold]

The following is an FA over alphaber Σ = {a, b, c}. Prove that it accepts all strings that have an odd number of occurrences of the substring abc.(top one)
1
vote
1answer
29 views

Regular and not Regular Grammar

According the Peter Linz Book, am a confusing about the two example the Grammar G1 = ({S},{a,b},S,P1) with P1 given as S -> abS|a and G2 = ({S,S1,S2,},{a,b},S,P2) S -> S1ab S1 -> S1ab|S2 S2 -> a ...
1
vote
1answer
38 views

minimum number of states for the regular expression

Could somebody please tell me if there is a way to create a DFA with 8 states for the regular expression $$(111 + 11111)^*$$ I was able to create a DFA with 8 states, but the place I saw the question ...
1
vote
1answer
12 views

Why is it that the transition function for DPDA's only works for 1 alphabet symbol, and 1 stack symbol?

Why is it that the transition function for DPDA's only works for 1 alphabet symbol, and 1 stack symbol? Say f is the transition function, why does having ...
0
votes
2answers
29 views

Automaton accepting $\{a^{2i}bc^{2k} \mid i, k \in\mathbb{N}\}$

How can I produce an automaton accepting $\{a^{2i}bc^{2k} \mid i, k \in\mathbb{N}\}$? I am essentially confused about exactly what the $2i$ and $2k$ mean. Does that mean that the automaton only ...
-1
votes
1answer
16 views

Regular expression syntax

am a little confused by regular expression to convert to NFAs. am actually test using http://www.regexr.com/ but some of regular expression like a*+ab is that mean (a*)+ is that correct .. ...
4
votes
0answers
49 views

context free grammar to NFA

I've been given an exercise to solve which goes as follows: generate an NFA from the given CFG, $$\begin{align*}S &\to AB \mid c\\ A &\to aAb \mid c\\ B &\to bBa \mid c\ . \end{align*}$$ ...
3
votes
1answer
20 views

Automata for languages derived from an automaton by number of state visits

My question in response to this answer: what would the finite automata look like for $L_1$ and $L_0$ in the answer? I get how the languages are formed; however, since $M_L$ cannot remember how many ...
2
votes
1answer
43 views

Finite Automata — Determine if a set is regular

I have been at this for hours. The question is: Prove that the language $A = \{0^kx \mid k > 0, x \in \{0,1\}^*, \text{ and } \#(0,x) \geq k\}$ is regular, where $\#(n, x)$ denotes the ...
1
vote
0answers
43 views

Using A* to find the word closest to an input rejected by a finite automaton

In the article Fast approximate string matching with finite automata by M. Hulden (2009) (mostly pages 58/59), the author describes how to search for a closest matching string word from an automaton ...
2
votes
1answer
60 views

Help on using the pumping lemma?

I'm trying to prove that a language is not regular. That language is: {w ∈ {a, b}* | amount of a's in w is equivalent to the amount of b's in w, mod 2}. I have an inkling that this language is not ...
-2
votes
1answer
40 views

NFA: Regular Language that starts with ab but does not end with ab?

$L = \{x \in \{a,b\}^* \mid \text{$x$ starts with $ab$ but does not end with $ab$}\}$ I'm having trouble making a table for this NFA. I tried a few sketches out of the diagram and I can post them ...
1
vote
1answer
71 views

How to write a DFA where the second digit is equal to the last digit of binary strings?

I'm having some trouble writing a DFA for the language $$\{w =b_1\dots b_k \in\{0, 1\}^* \mid b \ge 2 \text{ and } b_2=b_k\}\,.$$ What I thought for this is writing a DFA where there are 4 states, ...
0
votes
1answer
55 views

Decide whether DFA have useless states

A useless state in a DFA is one that is never entered on any input string. Consider the problem of determining whether a DFA has any useless states. Formulate this problem as a language and show that ...
6
votes
3answers
862 views

How to XOR automata?

Say we have 3 DFAs. We know how to OR, AND, or NOT them. But how does one XOR them? There is not one single mention of this online. $x\; \mathrm{XOR} \;y\; \mathrm{XOR} \;z = ((x|y)(\neg x|y)|z) ...
2
votes
1answer
32 views

Property of two ANEAs is in NP

I have two arbitrary acyclic nondeterministic finite automata $\mathcal{A_1}$ and $\mathcal{A_2}$ and want to show that the problem $L(\mathcal{A_1}) \not \subseteq L(\mathcal{A_2})$ is in NP by ...
3
votes
1answer
97 views

Efficient simulation of an NFA, while preserving the paths to the accept states

The standard way of simulating an NFA on a computer (for implementing regex engines etc) is to construct a DFA that accepts the same language. Otherwise you get problems like exponential blowup. ...
0
votes
0answers
16 views

DFA transtion table [duplicate]

I have the following DFA transition table for the regular expression ab. I don't understand these hyphens.As we know DFA is a deterministic automata and each state is defined for both a and b. ...
-3
votes
1answer
55 views

Creating a DFA that only accepts number of a's that are multiples of 3

I am brand new to DFA's and my first exercise requires me to create a DFA instance such that the number of a's in the string is a multiple of 3. We only have two types of symbols: a, b. To my ...
0
votes
2answers
55 views

What does an NFA do if there's no transition with the correct symbol?

So I am learning about DFA and NFA, and I need some clarification for it. DFA accept empty set transition for every element in the alphabet path are deterministic NFA accept the empty set ...
0
votes
2answers
49 views

Help designing a Turing Machine

I am faced with the following question: Design a Turing Machine that recognizes the language $L = \{1^{2n+1}\mid n \text{ is a non-negative integer}\}$. Show the state diagram. I started doing ...
5
votes
2answers
274 views

Detecting palindromes in binary numbers using a finite state machine

In my first algorithms class we're creating these patterns that are supposed to model a finite state machine. We were given a task to think if we can figure out a way to detect palindromes in binary ...
3
votes
2answers
43 views

Finding out if languages involving counting and modulo operations are regular

I am having trouble with the regularity of the two following languages: i) $\{0^{n}1^{m}|n,m>0,n-m=0\,mod\,3\}$ ii) $\{0^{n}1^{m}|n,m>0,n+m=0\,mod\,3\}$ To clarify this is stating that the ...
1
vote
2answers
86 views

Show that for any natural number n, there is a regular language that is not recognized by any DFA with at most n final states

Just as the question asks, I am trying to understand the relationship between the number of accept states a DFA has (not necessarily the total number of states) and the languages it can accept. I ...
-1
votes
1answer
100 views

How to determine the set of numbers read by a DFA from one state to another?

Using the Deterministic Finite Automaton (Q, Σ, Δ, q_0, F): Alphabet: Σ is {(0 0), (0 1), (1 0), (1 1)} Definition of Δ to strings recursively: Δ*(q, ε) = q for all q ∈ Q Δ*(q, xa) = Δ(Δ*(q, x), ...
0
votes
1answer
86 views

DFA for every run of a's=2 or 3

I am trying to create a dfa for L={w: every run of a's has length either two or three} this is my attempt at the solution..i feel like I am missing something..?
3
votes
1answer
48 views

Using induction to prove transition states are the same

Suppose that you have a DFA $M=\left(S,\Sigma,s_0,\delta,{s_f}\right)$ with $s_f\neq s_0$. Suppose further that, for all $a\in\Sigma$, $\delta\left(s_0,a\right)=\delta\left(s_f,a\right)$. Show that ...
0
votes
2answers
89 views

What does it mean to prove that a set of binary integers is regular?

I'm not exactly sure what this question is asking me to do: Show that the set of binary integers (given as strings over $\{0, 1\}$) that are divisible by $3$ is regular, by giving a DFA that ...
0
votes
1answer
54 views

Is a door lock a finite state machine?

Must the states of a finite state machine be worked off sequentially or could you understand the different shaped parts of the key as input and the position of the pins as states? If not all the input ...
1
vote
1answer
27 views

Why does a DFA either contain all or no words $a^k$ if it loops for $a$ in all states?

I am trying to solve this particular problem from Automata Theory by Ullman, Hopcroft, it is as shown below: Let $A$ be a $DFA$ and $a$ be a particular input symbol of $A$, such that for all ...
4
votes
0answers
34 views

Languages recognized by finite state automata of polynomially growing size

In the course of my research (condensed matter physics stuff), I stumbled over the following concept: The class of regular languages can be defined via finite state machines (FSM): A language $L$ ...
0
votes
1answer
159 views

Converting NFA to regular expression [duplicate]

Here is the regular expression I made for it This is my first answer, used the naive method aka don't know what am doin' method. $$ \epsilon \cup a^* \cup (a^*b) \left((a| b^*a) | \left( ...
1
vote
1answer
69 views

Don't understand closure under string reversal

I am trying to learn from http://www.cs.uiuc.edu/class/su08/cs273/lectures/lect_06.pdf #2 and I understand everything except for the 2nd line of delta prime prime function, I having breaking down ...
1
vote
0answers
77 views

Given a non-deterministic Mealy machine $M$, if $L$ is regular, is $M(L)$ regular?

Consider a nondeterministic Mealy machine, $M$, defined as follows: $M = (Q, \Sigma, \Delta, \delta, \tau, q_0)$ where $Q$ is a finite set of states $\Sigma$ is an input alphabet $\Delta$ is an ...
0
votes
1answer
135 views

Show that the regular languages are closed against taking “the second half” [duplicate]

Given $L$ is regular, the proof that $\mathrm{HALF}(L)$ is regular is pretty straightforward to me (e.g., #11 in this link): simply making a NFA and meeting in the middle with 2 original DFAs, the ...
2
votes
2answers
55 views

Method for measuring the 'similarity' between FSA grammars?

I'm working with a pattern matching algorithm that generates an acyclic finite state automaton that accepts a given text string and all its substrings. The FSA algorithm is being run on a symbolic ...
-4
votes
1answer
65 views

Determine if DFAs accept any word which contains bb [closed]

Let $\Sigma=\{a,b,c\}$. Describe an algorithm that takes as input a deterministic finite automaton $M= (Q,\Sigma,\tau,s,A)$ and determines whether or not $M$ accepts a word containing $bb$ (i.e., a ...
1
vote
1answer
30 views

Sampling from a Acyclic Deterministic Finite Automaton

Assume you have a finite language $L$ succinctly represented as a acyclic DFA $M$ (models can't be much simpler than that :) ). How can we efficiently sample a word from $L$ with uniform ...
-1
votes
1answer
35 views

Do NFAs with ϵ-transitions accept languages that no PDA can?

Is it correct to say that there are languages that a NFA with epsilon recognizes but a PDA is not? I think that it is wrong but I cannot find a suitable explanation.
1
vote
1answer
213 views

Deciding if a finite automata accepts strings of any length

Question is you're given a DFA. Give an algorithm which tells you whether strings of all lengths $n\in \mathbb{N}$ are acceptable or not. What I doing was, I have algorithm to count the number of all ...
3
votes
1answer
48 views

Converting generalized NFAs to NFAs

I came across generalized nondeterministic finite automata (GNFAs) in Sipser's Introduction to the Theory of Computation. These are automata where transitions are labelled with regular expressions, ...
-1
votes
1answer
127 views

How to construct a DFA for this?

Let $C = shuffle(A, B)$ denote the shuffle $C$ of two languages $A$ and $B$, it consists of all strings $w$ of the form $w = a_1b_1a_2b_2....a_kb_k$, for $k > 0$, with $a_1a_2 ··· a_k \in A$ and ...
-1
votes
1answer
53 views

Why is there still nondeterminism in my automaton?

I've been solving some exercises recently and it appears my answer was wrong for this particular example. The task is to convert this NFA into a DFA: My attempt is this: Now the tool I'm using ...
-3
votes
1answer
65 views

Language of a grammar

What's the language of following grammar? $G: S \to S_1B$ $S_1 \to aS_1b$ $bB \to bbbB$ $aS_1b \to aa$ $B \to \lambda$ any hint or solution?
2
votes
6answers
407 views

Regular expression (ab U a)* to NFA with two states (Sipser)?

In the 3rd edition of Sipser's Introduction to the Theory of Computation (example 1.56, p.68), there is a step-by-step procedure to transform (ab U a)* into a NFA. And then the text ends with: "In ...