6
votes
3answers
196 views

I need clarification about DFA's and DFA acceptable languages

In class yesterday we went over DFA's and DFA acceptable languages. An example of a language that is not DFA acceptable was given as $\{ ab, aabb, aaabbb, aaaabbbb, \ldots \}$. The reason given was ...
2
votes
3answers
159 views

Does there exist a proof of closure of regular languages under regular substitution by giving the corresponding DFA?

Every proof I can find of this result is by way of regular expressions. Is there any "constructive" proof that defines the corresponding DFA (probably NFA)? For instance the proof of concatenation ...
1
vote
1answer
31 views

Proof that $A_{DFA}$ is decidable in Sipser

It seems like the proof that $A_{DFA}$ is decidable in Sipser (2nd ed.) assumes the computation will halt... and hence only really proves that $A_{DFA}$ is recognizable. The language $A_{DFA}$ is ...
9
votes
1answer
120 views

How fast can we decide whether a given DFA is minimal?

Minimizing deterministic finite automata (DFAs) is a problem that has been thoroughly studied in the literature, and several algorithms have been proposed to solve the following problem: Given a DFA ...
2
votes
1answer
87 views

showing that the pair of Finite Automata are equivalent

Here I am trying to show that the pair of Finite Automata are equivalent. I have tried something but I am not sure if I am in the right direction. This is what I have. These are pairs of FA's. Set ...
10
votes
4answers
497 views

Regular language not accepted by DFA having at most three states

Describe a regular language that cannot be accepted by any DFA that has only three states. I'm not really sure where to start on this and was wondering if someone could give me some tips or ...
1
vote
1answer
79 views

Can reversing the final and non-final states of a DFA produce the complement of the original language?

Is this true? If I change all final states of a given Deterministic Finite Automata to non final states and all non final states to final states then does this new automata represent the complement of ...
3
votes
1answer
72 views

NFA to DFA final states proof

When translating an NFA into an equivalent DFA, we can say that all states that contain the final states of NFA, is the final state of DFA. What should my arguments be in order to prove this? ...
1
vote
1answer
40 views

Finite Automata Input Confusion

I am looking at the following non-deterministic finite automata which accepts all strings that end with at least 2 bs. I am wondering what would happen when you have the input string 'abba' with this ...
6
votes
2answers
130 views

Partition an infinite regular language into 2 disjoint infinite regular languages

Given any infinite regular language $L$, how can I prove that $L$ can be partitioned into 2 disjoint infinite regular languages $L_1, L_2$? That is: $L_1 \cup L_2 = L$, $L_1 \cap L_2 = \varnothing$, ...
1
vote
0answers
57 views

Flowcharts vs DFA resp FSM equivalency

First I apologize if I confused therms DFA and FSM, to me it seems that is the same thing. The question is simple: Are the flowcharts (sequence, branching and jumping) equivalent to DFA resp. FSM? I ...
0
votes
3answers
393 views

NFA or DFA for strings the contain exactly twice substring ab?

Given the language with alphabet: $\{a, b, c\}$ Draw an NFA or DFA for all the strings that have exactly twice substrings $ab$ and at least on $c$. I'm stuck with "exactly twice $ab$". Can somebody ...
3
votes
1answer
107 views

Abstract machine that can recognize repetition

Let $C$ be an infinite set of characters. I'd like an abstract machine which can recognize sequences consisting of $k$ (constant) of repetitions of a char from $C$. For example, if ${x,y,z} \subset ...
0
votes
2answers
442 views

DFA/NFA/ε-NFA: subsetting each other or different sets?

I know that an ε-NFA (NFA with epsilon transitions) is not an NFA or a DFA and an NFA is not a DFA. HOWEVER, say you have a complete DFA. Isn't that theoretically an NFA and an ε-NFA? Just because it ...
6
votes
1answer
176 views

For what kinds of languages is min |NFA| = Ω(min |DFA|)?

Consider a regular language $L$. Let $D(L)$ be a minimal DFA for $L$ and $N(L)$ be a minimal NFA for $L$ (minimal in the sense of the smallest possible number of states for an automaton that ...
2
votes
1answer
224 views

DFA drawing for binary string with substrings of minimum length 3 with at least two zeroes in each substring

In trying to gain a better understanding of finite state machines, I stumbled across this idea and have been confused as to how to approach this case in terms of a DFA. The set of binary strings ...
2
votes
2answers
339 views

DFA - Equivalence classes

I am preparing for my exam in formal languages and I need some help with one question from one old exam. I know that the number of equivalence classes of some regular language L, is the number of ...
1
vote
4answers
1k views

Designing a DFA that accepts strings such that nth character from last satisfies condition

This is a homework question, so I am only looking for hints. I got a question in an assignment which states : Design a DFA that accepts strings having 1 as the 4th character from the end, on the ...
7
votes
1answer
129 views

Results on the languages recognized by undirected DFAs

For my Bachelor's thesis, I consider the class of languages recognized by symmetrical DFAs, that is, deterministic (complete) finite automata satisfying the following condition: Let $A$ be a ...
8
votes
1answer
135 views

What is the complexity of the emptiness problem for 2-way DFAs?

I'm wondering, what is the time-complexity of determining emptiness for 2-way DFAs? That is, finite automata which can move backwards on their read-only input tape. According to Wikipedia, they are ...
6
votes
3answers
205 views

Algorithm to shrink a DFA by introducing nondeterminism?

This is somewhat related to another question I asked, but I feel it's different enough to warrant its own question. I'm doing research where I'm trying to find the structure of complements of a ...
4
votes
3answers
152 views

Are there algorithms to exactly minimize NFAs which are sometimes efficient?

I'm doing some research with NFAs, and I'm wondering there are algorithms which quasi-efficiently minimize them. I realize that this problem is $PSPACE$ hard, so I'm not looking for a polynomial time ...
2
votes
1answer
136 views

Are HTML and CSS regular languages?

I have a question whether or not CSS and HTML are regular languages. I believe CSS is a regular language, since it should be possible to create a regular expression to match the structure of CSS. ...
5
votes
1answer
121 views

Nondeterministic finite state machine without any initial state possible

Is it theoretically possible to have a nondeterministic finite state machine without any initial state or does it need at least one initial state?
0
votes
2answers
662 views

How to convert NFA with null moves to NFA without null moves?

I am converting NFA with $\varepsilon$-moves to the NFA without $\varepsilon$-null moves. I understand that if, there is a $\varepsilon$-move between, $q_i$ and $q_j$, then all edges from $q_j$ have ...
6
votes
2answers
107 views

Classes of NFAs which allow efficient subset testing or unambiguity conversions

I'm doing some research regarding NFAs and inclusion problems with them. I know that in general, the inclusion problems, and converting to an unambiguous NFA, are both PSPACE-complete. I'm wondering, ...
4
votes
2answers
222 views

Why is the following language not context-free?

$L = \{a^n b^m | m \not= n^2 \}$ I guess I need to use Pumping Lemma for CFL in order to prove this. But I'm stuck. Assuming that $ a^n b^m = uvxyz$, we know that $v$ or $y$ can not have both $a$ ...
8
votes
1answer
170 views

Difference between the languages accepted by two DFAs with different initial state/accepting states?

Recently, I asked a question on Math SE. No response yet. This question is related to that question, but more technical details toward computer science. Given two DFAs $A = (Q, \Sigma, \delta, q_1, ...
1
vote
1answer
134 views

Is The Following Language Regular? [duplicate]

Let $L_{1}$ and $L_{2}$ be 2 languages over the same alphabet $\Sigma$. $$A(L_1,L_2)=\{x\in \Sigma^*|\exists y,z\in L_2\text{ such that } yxz\in L_1\}$$ Assume that $L_{1}$ is regular and $L_{2}$ ...
2
votes
3answers
92 views

How does “δ:Q×Σ→Q” read in the definition of a DFA (deterministic finite acceptor)?

How do you say $\delta\colon Q \times \Sigma \to Q$ in English? Describing what $\times$" and $\to$ mean would also help.
3
votes
1answer
483 views

DFA that accepts decimal representations of a natural number divisible by 43

First, I have tried to build a DFA over the alphabet $\sum = \{0,\dots, 9\}$ that accepts all decimal representations of natural numbers divisible by 3, which is quite easy because of the digit sum. ...
2
votes
1answer
198 views

Does this DFA have a solution?

I am trying to create a DFA that can recognize strings with alphabet $\{a,b,c\}$ where $a$ and $c$ appear even number of times and where $b$ appears odd number of times. I am wondering that this may ...
1
vote
1answer
70 views

Finite State Automata for recognising consecutive characters

I'm currently working on this question as part of some homework, it has me stumped. I'm familiar with finite state automata (FSA), I know how they work and I've read everything I can find on ...
6
votes
3answers
255 views

Proving the language which consists of all strings in some language is the same length as some string in another language is regular

So I've been scratching my head over this problem for a couple of days now. Given some language $A$ and $B$ that is regular, show that the language $L$ which consists of all strings in $A$ whose ...
2
votes
1answer
983 views

Simplification of regular expression and conversion into finite automata

This is a beginners question. I and reading the book "Introduction to Computer Theory" by Daniel Cohen. But I end up with confusion regarding simplification of regular expressions and finite automata. ...
0
votes
1answer
330 views

How do you prove that two languages are equivalent?

How can you show that the Language accepted by an NFA and the reverse NFA is the same? For a language $L$, there is an $L^R=\{ w^R \mid w \in L\}$ Let's say that $w^R$ is the string obtained by ...
2
votes
3answers
395 views

NFA for binary words that do not end in 10

Construct an NFA over $\{0, 1\}$ whose language contains only words that do not end with $10$. This is one of the first problems in the book, so it's supposedly easy. I just can't figure it out. ...
7
votes
4answers
5k views

How to show that a “reversed” regular language is regular

I'm stuck on the following question: "Regular languages are precisely those accepted by finite automata. Given this fact, show that if the language $L$ is accepted by some finite automaton, then ...
5
votes
1answer
131 views

Is the set of minimal DFA decidable?

Let $\mathrm{MIN}_{\mathrm{DFA}}$ collection of all the codings of DFAs such that they are minimal regarding their states number. I mean if $\langle A \rangle \in \mathrm{MIN}_{\mathrm{DFA}}$ then for ...
5
votes
3answers
140 views

Is the set of codes of Deterministic Finite-State Automata a regular language?

Let $\Sigma$ be a given alphabet. Is there a way to code up Deterministic Finite state Automata (DFA) over $\Sigma$ as strings of $\Sigma$ in such a way that the corresponding subset of $\Sigma^*$ is ...
4
votes
2answers
2k views

Proof that union of a regular and a not regular language is not regular

Let $L_1$ be regular, $L_1 \cap L_2$ regular, $L_2$ not regular. Show that $L_1 \cup L_2$ is not regular or give a counterexample. I tried this: Look at $L_1 \backslash (L_2 \cap L_1)$. This one ...
0
votes
2answers
448 views

Are supersets of non-regular languages also non-regular?

I have to proof that if $L_1 \subset L_2$ and $L_1$ is not regular then $L_2$ it not regular. This is my proof. Is it valid? Since $L_1$ is not regular, there does not exists a finite automata $M_1$ ...
2
votes
1answer
446 views

Automata that recognizes Kleene closure of permutations of three symbols

This is an automata theory homework question. I need to create DFA that meets the following criteria: Alphabet $\Sigma = \{ a, b, c \}$ Machine accepts empty string and strings of length that is ...
-1
votes
1answer
164 views

construct regular expression

I need help with the following exercise: Construct an $\varepsilon$-NFA for the following regular expression $(a|\varepsilon)(ba)^*(c^*a|bc)^*$. i already tried this exercise with nerode but i didnt ...
24
votes
4answers
14k views

How to convert finite automata to regular expressions?

Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms, e.g. Thompson's algorithm. The other direction seems to be more tedious, though, and ...
6
votes
1answer
966 views

Prove that regular languages are closed under the cycle operator

I've got in a few days an exam and have problems to solve this task. Let $L$ be a regular language over the alphabet $\Sigma$. We have the operation $\operatorname{cycle}(L) = \{ xy \mid x,y\in ...
5
votes
3answers
635 views

If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?

I'm am stuck solving the next exercise: Argue that if $L$ is context-free and $R$ is regular, then $L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} $ (i.e. the right quotient) is ...
20
votes
2answers
543 views

Why is a regular language called 'regular'?

I have just completed the first chapter of the Introduction to the Theory of Computation by Michael Sipser which explains the basics of finite automata. He defines a regular language as anything ...
1
vote
1answer
308 views

Non-regular Languages? [duplicate]

Possible Duplicate: How to prove that a language is not regular? Why $L_a$ and $L_b$ are not reguluar? $L_a = \{ e^i f^{n-i} g^j h^{n-j} : n \in N, 1 \leq i, j \leq n \}$. $L_b= ...
4
votes
2answers
248 views

DFA with limited states

Lets $L_z \ := \{ a^i b^i c^i : 0 \leq i < z \}$ $\{a,b,c\} \in \sum^*$ there is a DFA with $\frac{z(z+1)}{2}+1$ states - How can I prove this? And I need largest possible number $n_z$, for ...