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.
1
vote
2answers
34 views
DFA for words with $a$s not a multiple of 3 and at least one $c$
Consider this language: $$L = \{w \in \{a,c\}^* \mid 3\nmid\#a(w)\land\#c(w)>0\}$$.
Here is an automaton for the first part of language, but I do not know how to devise and attach the second part ...
-1
votes
0answers
14 views
DFA of numerical addition
Give a DFA for Σ = {0, 1, 2, 3, 4} that recognizes strings over the alphabet 0, 1, 2, 3, 4 which are integers with a digit sum of 6 and may have leading zeros. For example, 1230 should be in the ...
0
votes
0answers
31 views
how to convert from DFA to PDA with only 3 states
I think basically DFA is similar to PDA without the stack, so is it possible to translate an arbitrary DFA to a PDA with only three states?
1
vote
1answer
19 views
How do I convert the following GNFA to regular expression?
Here is a GNFA I made from an NFA.
I'm unsure how to treat the node of b(a∪b)* (the first node after the start node and the one below it). Since it doesn't lead to any goal state, do I disregard it ...
0
votes
0answers
11 views
Minimisation Steps for DFA
I want to apply minimisation on this DFA, what techniques or steps can I use? Is there any procudure for this?
I think state c and e are extra but I do not know how to justify it.
1
vote
3answers
63 views
Give a $3$-state DFA for $(01 \cup 1)^∗$
How do I change the design to accept the given language, because I think my DFA can accept $001$ as well. Is that correct?
-3
votes
0answers
20 views
can anybody solve this question for me? [closed]
i have to construct DFA for the language of alphabet {0,1}.
0
votes
2answers
26 views
How to deal with character set in regular expression?
In regular expression implemented by language like perl or python, user can write a set of characters like [123abcd] or special notation like \d to represents digit ...
0
votes
1answer
35 views
Prove that $SEQ_{DFA}$ = {⟨A,B⟩ | A,B are DFAs and L(A) ⊆ L(B)} is decidable
Consider the following language $$EQ_{DFA} = \{ \langle A, B\rangle: A \ and \ B \ are \ DFAs \ and \ L(A) = L(B)\}$$
Given the fact that $EQ_{DFA}$ is decidable, how can I prove that the language $$...
1
vote
1answer
52 views
How to minimize this DFA using given algorithm?
I am trying to use Myhill-Nerode theorem to minimize the DFA appearing below.
The algorithm repeatedly runs the following step:
If there is an unmarked pair $(Q_i, Q_j)$, mark it if the pair $\{δ (...
0
votes
0answers
16 views
Is the set obtained by taking the first quarter of strings from a regular set $L$ regular as well? [duplicate]
That is, let $L'$ be the set consisting of the first quarter (first $\frac{1}{4}^{th})$ of each string whose length is divisible by 4 in a regular set L. I am pretty sure $L'$ is regular, but I am not ...
2
votes
1answer
42 views
Are there problems that are DSPACE(O(1)) complete?
I know there are problems that are NL-complete, NP-Complete, PSPACE-complete, etc. Are there problems that are DSPACE(O(1))-complete I.e. NSPACE(O(1))-Complete I.e. Reg-Complete?
Thanks!
0
votes
2answers
115 views
How does modulus affect the regularity of language?
the question is as follows, further the notation used are standard as used in theory of computation
$$L = \big\{ w : w \in \{a,b\}^*,\ |n(a) - n(b)| = 2k\}\,.$$
Beware 'K' is not a fixed integer its ...
1
vote
1answer
20 views
Understanding NFA (nondeterministic finite automaton) with a null transition
I'm reading Computer Science: An Interdisciplinary Approach. It mentioned an NFA (nondeterministic finite automaton) with a null transition, as shown above, recognizes all binary strings that do not ...
0
votes
2answers
62 views
Does there exists a finite automata for the given language?
The question is simple and given as, $alphabets=\{a, b\}$, and language $L$ over them as:
$L = \{w: w \ € \{a, b\}^*, (n(a) - n(b)) \ mod \ 3=1\}$. Here $n(a)$ = number of $a$ and $n(b)$ is number of ...
2
votes
1answer
119 views
Is there a polynomial time algorithm to tell if an NFA over an unary alphabet is universal?
Given an Nondeterministic Finite State Automaton with $n$ states over an unary alphabet, is there some algorithm to check if the automata is universal in time polynomial in the number of states?
I ...
0
votes
0answers
18 views
Proof by induction on “Equivalence of NFA, ε-NFA”
I would appreciate if anyone could help me out with the portion of the proof where I have to construct an NFA from an $\epsilon$-NFA. I do know that doing it otherwise is easy. I am new to the concept ...
0
votes
2answers
35 views
DFA that accepts a*b*c*
Beginner in DFA related studies, was trying to figure out how to create a DFA with {a,b,c}, that can recognize a * b * c *.
Appreciate the help.
2
votes
1answer
36 views
Proving formula for derivative of Kleene star
Prove that for any symbol $a$ and regular expression $r$ it is true that:
$$\partial a(r^* ) = \partial .a(r)(r^* )$$
My attempt:
Induction on regular expression $r$
Base cases:
1) $\...
2
votes
1answer
64 views
Closure of regular languages under deleting a 1 from each even run of 1s
Let $R$ be a regular set over the alphabet $\{0, 1\}$. Give a machine construction to prove that the set obtained by deleting one 1 from each even length block of 1’s is also regular, and using ...
2
votes
3answers
361 views
Are all finitely recursive context free languages parseable with a regexp?
Let's say I have a context free language. It can be recognised by a pushdown automaton. Chances are it can't be parsed with a regular expression, as regular expressions are not as powerful as pushdown ...
2
votes
1answer
46 views
Digraph vertices: classification by counting outgoing walks
I'm reproducing a question I posted on MSE (yet with no answer both there and by myself).
Given a (finite) directed graph $G = (V, E)$. For each vertex $v \in V$ and a natural number $n$, let $W_v(n)$...
-1
votes
0answers
24 views
How can I prove that the language is regular for the following: {w|w contains an equal number of occurrences of the substrings 01 and 10} [duplicate]
I was able to come up with both the DFA and NFA, but I have no idea how to prove that the language is regular. Any help would be great!
0
votes
0answers
30 views
regular language for NFA [duplicate]
I'm trying to find the w-regular language of this NBA. In 'Principle of Model Checking' - Book there's an algorithm for this problem:
1. Take the NBA as NFA and create the regular language to get from ...
0
votes
1answer
19 views
Why do we take null closure two times while converting from Epsilon-NFA to NFA?
I am studying Theory of Automata. I was studying conversion of Epsilon-NFA to NFA. I had to take null closures of states two times, before and after the specific input.
Could someone explain, what is ...
1
vote
1answer
32 views
How to implement a maximal munch lexical analyzer by simulating NFA or running DFA?
I'm planning to implement a lexical analyzer by either simulating NFA or running DFA using the input text. The trouble is, the input may arrive in small chunks and the memory may not be enough to hold ...
4
votes
1answer
50 views
Efficiently convert an NFA with multiple $\varepsilon$ edges and accepting states into a regular expression
Given an NFA with alphabet $\Sigma = \{a, b, c\}$ defined in the diagram, is there a way to efficiently convert it into a regular expression?
The way I solved this problem is to first convert the NFA ...
6
votes
2answers
294 views
Find the language an NFA recognizes
For example, I have an NFA $A_n$ with alphabet $\Sigma = \{0, 1\}$.
The language recognized by this NFA is known to be $\{u1v\ |\ u, v \in \Sigma^*, |v| = n − 1\}$.
I was unable to get the ...
0
votes
0answers
57 views
Proof: class of regular language is closed under union operation with different input alphabet
Tha class of regular lanugage is closed under the union operation.
If $A_1$ and $A_2$ are regular languages, then so is $A_1 \cup A_2$.
Thus, there are two finite automatons(FAs) $M_1$ and $M_2$ ...
1
vote
1answer
80 views
How many languages exist over the following alphabets?
(a) We have alphabet $\Sigma=\lbrace 1 \rbrace$, $\Sigma=\lbrace a,b \rbrace$ and (b) also an alphabet with size $k$ and words with length $n$.
For the first two alphabets in (a), we know that there ...
0
votes
1answer
16 views
Choose the best classifier to predict the label of strings of a regular language
I have to tackle this problem:
I have some strings that are my training set. These strings belong to a regular language corresponding to a deterministic finite automata (hidden namely I don't now it, ...
2
votes
1answer
26 views
Regular expression for capturing a “C-style” string
I have started to learn automata theory and languages. I am new to regular expressions.
As a use case in real world, I would like to construct a regular expression to accept a c-style string: ...
0
votes
1answer
44 views
Is the language $K=\{u \in\{0,1\}| n \geq 0, \forall_{v \in\{0,1\}^n} (u+v) \in L \}$ regular?
For two words $w,v \in\{0,1\}^*$ of equal lenght, let $w+v \in\{0,1,2\}^*$ denote the word in which the $i$-th word is the sum of $i$-th position of $w$ and $v$, as follows: if $w=a_1 \ldots a_n$ and $...
0
votes
1answer
50 views
what are the conditions for two NFAs to be equivalent?
It's a pretty basic question, but I couldn't find an explicit answer in the book which I'm using, also when searching for it - I didn't find a reliable reference.
Correct me if I'm wrong but for two ...
0
votes
1answer
45 views
Finite state automaton for the reverse of the language, and multiple starting states
I am studying about Finite State Automaton, and I found that the when reversing a language (i.e., transforming $L$ to $L^R$), I have to add new start state. Why is that?
Also, can a Finite State ...
0
votes
1answer
51 views
Is there a proof that shows why DFAs can't be used to show the concatenation of two regular languages?
Sipser goes on to show that regular languages are closed under concatenation using NFAs. His proofs typically use NFAs to prove closure under the operations.
Is there an alternative proof that goes ...
0
votes
0answers
13 views
Definition of string-generation for NFAs
I am new to automaton theory, and I am currently trying to think my way through the basic concepts. Since I come from a linguistics perspective, I find it helpful to think of automatons as string-...
2
votes
2answers
129 views
Is DFA and Regular Expression equivalent?
The language of a DFA can be the empty set (by defining no final states), but can a Regular Expression do that?
If Regular Expression cannot do that, does it mean that DFA and Regular Expression are ...
6
votes
3answers
1k views
How to prove using pumping lemma that language generated by a(b*)c(d*)e is regular?
I am studying pumping lemma from Introduction to theory of computation by Michael Sipser. I wanted to check if the language generated by regular expression
...
1
vote
2answers
131 views
Algorithm for printing all accepted strings (to an upper bound if infinite amount) from a given DFA
As the title states I'm trying to write an algorithm that generates accepted strings to an upper bound from a given DFA.
It should not generate more strings than the upper bound n if it contains ...
1
vote
1answer
30 views
Regular expression of 011=110 in string
What is the regular expression for language containg no. of 011 equal to 110 in string ?
1
vote
2answers
41 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,...
4
votes
1answer
57 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
45 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
50 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
40 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
60 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
59 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
287 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
36 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, ...
