Stack Exchange Network

Stack Exchange network consists of 174 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
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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.

0
votes
1answer
17 views

Regular expression of 011=110 in string

What is the regular expression for language containg no. of 011 equal to 110 in string ?
0
votes
2answers
25 views

Understanding $\epsilon$ transitions on NFA

I can't understand why $\epsilon$ is accepted. I thought if $\epsilon$ is inputed then it would go from $q_1$ to $q_3$. $a$ is also accepted, but I though if $a$ is inputed then then the NFA would die,...
3
votes
1answer
41 views

Is the symmetric difference of a non regular language L and a finite language f non regular?

The symmetric difference of $L_1$ and $L_2$ is defined to be: $(L_1-L_2) \cup (L_2-L_1)$. Problem: I’m trying to prove that given L a non regular language and F a finite language there symmetric ...
0
votes
0answers
37 views

proving an automaton language for the language over $\{a,b\}^{*}$ : $w\in L$ if $aa$ is not an infix of $w$ ($aa$ doesn't appear in $w$)

I built the next automaton: I have problem to prove $L = L(q_0)\cup L(q_1)$, (when $L(q)$ denotes words $w$ such that $\hat{\delta}(q_0,w) = q$ at a given DFA) because semantically $L(q_0)$ is the ...
1
vote
2answers
43 views

Is two arrows on each state necessary in DFA? [duplicate]

In DFA, is two arrows on each state necessary? Or it depend on language alphabets? I mean if there is $\Sigma = \{a\}$ then there should be one arrows on each state. OR if there are $\Sigma = \{a ,...
-2
votes
2answers
32 views

Justifying regular language

I have been given the question "Is the language 010 ∪ 101 regular? Justify your answer." It is regular and as it can be accepted by an NFA (Draw NFA). Is this correct?
3
votes
1answer
39 views

Why does everyone say that NFA guesses it's next state?

In the picture above e is an empty string, and a is a symbol from an alphabet. Every book or professor I have heard from, says than when we make transitions in the NFA, the NFA must guess which state ...
4
votes
1answer
50 views

How do non-deterministic algorithms work on current machines?

I have some questions regarding the exact nature of non-deterministic algorithms. Is it right that non-deterministic algorithms do not rely on any randomness whatsoever? In which case, this Wikipedia ...
0
votes
1answer
54 views

How to convert DFA to regex with State Elimination

I can do the very simple transitions but it gets difficult when you have transitions jumping over 1 or more states. I have this difficult DFA i need help converting to RE: using STATE ELIMINATION ...
0
votes
1answer
27 views

Generation regular languages by context free grammar

I came across problem asking whether given statement is true and false. The statement given was as follows: Every Type-2 grammar can generate regular language. I felt that Type-2 grammar means, ...
0
votes
1answer
44 views

Drawing a NFA for a string

I have these grammar rules defined as follows, FDL -> FDEF FDL | ε FDEF -> #feature #: FEXP FEXP -> #op #( FLIST #) FLIST -> FEXP #, FEXP | #feature ...
0
votes
1answer
47 views

DFA that accepts two more $1$'s than $0$'s

What is the state diagram of a DFA that follows $L = \{w \in \{0,1\}^*\mid w\text{ has at least two or more 1's than of 0's}\}$. Examples: $110$ doesn't work, $1110$ works.
1
vote
1answer
19 views

Left quotient finite automata

This is very unclear to me. I understand what the left quotient is, however, can someone explain this: A={0,101} B=01,10,001} then how is A\B={1,01} I mean where are these strings extracted from? I ...
2
votes
1answer
63 views

Understanding application of Arden's theorem to find regular expression

I learnt Ardens theorem and its usage as follows: Ardens Theorem Let $P$ and $Q$ be two regular expressions over alphabet $Σ$. If $P$ does not contain null string, then $R = Q + RP$ has a ...
-1
votes
1answer
28 views

Regularity under set difference

Let L be a regular language. Then $\Sigma^{*} \backslash L^{*} = (\Sigma^{*} \backslash L)^{*}$ How do I prove it is wrong?
1
vote
1answer
16 views

Can we call deterministic equivalent of all NFA to be finite

Finite automata is defined as a simple machine having small memory. A deterministic equivalent of a NFA with n states will have O(2^n) states,so the number of states grow exponentially. So can we ...
1
vote
1answer
21 views

What will happen if input is larger than required in a NFA

This is my first time in the field of TOC so I am not able to provide any self-approach while asking .In the above example what will happen if input string is "1001" or "1111"?The state q4 can be ...
0
votes
0answers
19 views

Number of non deterministic finite automata that can be constructed for $n$ states and alphabet with $m$ symbols

I came across the fact that The number of DFAs that can be constructed for $n$ number of states and alphabet containing $m$ symbols is $n\times (\color{red}{n}^m)^n \times 2^n$ So I was wondering ...
0
votes
1answer
11 views

Simple path in a Finite Acceptor

What is the definition of a 'simple path' in a finite acceptor? My concern is whether self loops can be considered as a part of simple path from initial to final state?
1
vote
1answer
40 views

DFA for strings with number of 0's odd only in substring longer than 1

I'm trying to design and DFA that accept string with an odd number of 0`s, but counting only the ones within sub-strings with two or more 0. So, for example, 011000, will be accepted since it has 4 0`...
4
votes
2answers
91 views

Simplification of regular expression

I have some issue with how to simplify regular expression. I cannot find any suitable method to approach these types of problems. How would one approach simplifying the following regular expression: ...
2
votes
1answer
30 views

Why is $L := \{b^2a^nb^ma^3|m,n \geq 0\}$ a regular language?

(Pre-note: I'm learning Theory of Computation on my own, so bear with me if I'm saying something wrong/stupid.) Why is $L := \{b^2a^nb^ma^3\mid m,n \geq 0\}$ a regular language? This question ...
0
votes
0answers
19 views

How do I visualize this NFA? [duplicate]

There is a question that states: "Give an NFA that accepts the language over the alphabet {a, b} where words contain baa as substring or where any a is immediately followed by at least two b’s." I ...
0
votes
1answer
22 views

Type-0 grammar and terminal symbols

The question is pretty short, but I've been thinking about it quite some time: Are terminal symbols that are not in the defined alphabet still valid?
8
votes
5answers
2k views

Finite state automata: final states

In our programming language concepts course, our instructor claimed that it's okay for a final state to lead to another state in a finite state diagram. But this seems to be a fundamentally ...
1
vote
1answer
55 views

I can construct DFA for $a^{3n+1}$ but pumping lemma says it is not regular

Recently I stumbled across this language $L=\{a^{n}a^{{(n + 1)}^2-n^2} \in \Sigma^* \mid n\geq 0\}$ that I can rewrite as $a^{3n + 1}$. So I applied the pumping lemma to see if it is non regular, ...
1
vote
2answers
63 views

DFA impossible problem?

As you can see from the title this is the impression that i have on this problem, but probably it isn't impossible. The required DFA is : "The set of the strings with equal number of 0 and 1 such ...
-2
votes
3answers
65 views

is an empty string accepted by this NFA accepters

is the string epsilon(empty string) accepted by this NFA ?
1
vote
1answer
36 views

DFA complexity of reverse of language recognized by “maximal” DFA

Let's assume that DFA $A$ over the alphabet $\Sigma$ and with states $Q$ is maximal if for every function $f\colon Q\rightarrow Q$ there exists such word $w \in \Sigma^{*}$, that $q \cdot w = f(q)$ ...
-2
votes
1answer
34 views

give a nfa without ε-transitions corresponding to the Regular expression [closed]

Regular expression: (0 + 01)(ε + 1)1(ε + 0 + 1)* I dont know if my answer to this is entirely right but please enlighten me if i'm way out of line. \begin{array}{c|ccc} \ &0&1&\\\hline ...
2
votes
1answer
114 views

Understanding trap and dead state in automata

Well, this sounds somewhat basic definitions, but I feel they needs to be clearly defined. In book by Hopcroft et. al., there is an excerpt: ...a dead state, that is, a nonaccepting state that ...
1
vote
2answers
25 views

Number of states in NFA and DFA accepting strings from length 0 to n with alphabet Σ= {0,1}

The question is in title. Let me repeat: What are the number of states in NFA and DFA accepting strings from length 0 to n with alphabet $\Sigma = {0,1}$ I feel both NFA and DFA will take ...
1
vote
1answer
36 views

Determining whether $L^*$ is a finite union of $L^n$ for unary regular $L$

Give an algorithm that, given an NFA over a one-letter alphabet, determines whether the language it generates has the property that for some $n$, $$ L^* = \bigcup_{k=0}^n L^k. $$ I need some tips how ...
2
votes
1answer
30 views

unambiguous equivalent grammar

There is a grammar G given: S->XaX X->aX|bX|eps I just replied to the first question that was ...
2
votes
0answers
22 views

Minimization of simple cyclic automata

Version 1 of the question: I am looking for any correct $O(n)$ algorithm in the literature which will solve the DFA minimization problem referred to in the quote below from [Almeida & Zeitoun 2008]...
0
votes
0answers
38 views

Validating attempt on NFA to Regular Expression

So i tried turning the following NFA into a GNFA (first attempt). Please don't ask why i chose to do such a complex NFA on my first try, i just like the challenge i guess? ab is the concatenation of ...
1
vote
2answers
25 views

Closure of context-free languages under regular quotient [duplicate]

Knowing that $C$ is a context-free language and $R$ is a regular language, how to prove that $C / R = \{w| \exists x \in R: wx \in C\}$ is also a context-free language?
4
votes
1answer
71 views

The equational theory of regular languages has no finite set of axioms for general alphabets

According to Redko the equational theory of regular languages with operations $+, \cdot, *$ over a single letter has no finite set of axioms. Why does this imply that it has no finite set of ...
0
votes
0answers
19 views

Can the state removal (GNFA) method be directly applied to an NFA to get its equivalent regular expression?

Lots of lecture handouts or other materials I have found on the web say we can convert any DFA to an equivalent regular expression by converting it to a GNFA(Generalized Non-deterministic Finite ...
3
votes
1answer
45 views

What is the connection between combinatorial circuits and finite state automata?

The diagram on the Wikipedia page of FSA shows the hierarchy of the computational devices, in that diagram it is denoted that the finite state machines are superior to the combinatorial circuits. ...
0
votes
0answers
16 views

Trouble coming up with an expression to describe a DFA [duplicate]

This is a DFA that describes a language over {a,b} that only accepts a string if the number of a's in the string is not divisible by 3. I'm having difficulty coming up with an expression for it, I'm ...
0
votes
1answer
23 views

draw DFA with {w|w= Σ*0100}∩{w|w≠Σ*11Σ*}

So i need to draw a DFA for this language, i know i need to separate for 2 DFAs and than combine them both. What is the approach ? How do i do the $\Sigma^*$ inside the DFA ? The 0100 condition is ...
3
votes
2answers
59 views

The language of non-extendable strings of a regular language is regular

I recently came across this question in my textbook. $ \text{Let } L \text{ be a language over an alphabet } \Sigma \text{ that is accepted by some FSA.} $ $ \text{Prove that the language is also ...
1
vote
2answers
43 views

Do NFAs with $\varepsilon$-moves never terminate?

Suppose in an NFA we have an $\varepsilon$-move from a state $q_0$ to $q_1$. According to Sipser, Without reading any input, the machine splits into multiple copies one following each of the ...
1
vote
1answer
31 views

Are there algorithms for proving two finite state machines are equivalent?

Suppose we call two finite state machines equivalent if they "perform the same computation" - they accept the same language, or they produce the same output for any given input. Is there an algorithm ...
0
votes
1answer
28 views

Show that C(n) = {a^k | k is a multiple of n} is a regular language

I came across this question in an exam book and was unable to find a solution: Prove that C(n) = {a^k | k is a multiple of n} is a regular language for every natural number n ≥ 1. I wasn't able to ...
0
votes
1answer
34 views

Showing that there exists an algorithm, that converts NFA to DFA under some cirumstances

We are given NFA $A$, which for every input word $w$ has at most 10 runs over word $w$, beginning at the starting state. Show that there exists an algorithm, that converts such NFA to DFA in ...
0
votes
1answer
66 views

language accepted by DFA

what are the language that the DFA accept ? so my approach for the first one is : a needs to be 4n+1 for all n>=0, #b%2=0 also i found out there some loops inside the DFA and a:b ratio is 3:1 but ...
0
votes
0answers
35 views

Can we skip an input in push down automata

Hi here I'm giving a language L3={0^m 1^(n ) 2^m | m,n ∈ N} I designed this stack machine in order to accept this given language. Here I'm skipping 1 (no matter how many 1s are there) . Is it ok to ...
0
votes
1answer
43 views

How to do product construction with 2 DFA which has dead state

I have been trying to do a product construction(intersection) with 2 DFA which has dead states, but I'm stuck at the transition table with a confusion that,what should I do with dead state. Should I ...