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 ...
