1
vote
1answer
48 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 ...
0
votes
1answer
41 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
23 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 ...
-1
votes
1answer
26 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.
-3
votes
1answer
61 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?
4
votes
1answer
107 views

Counting the number of words accepted by an acyclic NFA

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. Can we compute $|L(M)|$ in polynomial time? If not, can we approximate it? Note that the number of words is not the same as the ...
7
votes
1answer
75 views

Smallest NFA accepting concatenations of two words of the length $k$ which are different at all positions

Let $k\in \mathbb N$ I'm looking for a small NFA build for the language of concatenation of two words of the length $k$ which are index-wise different, i.e. $$L_k=\{u\cdot v \in \Sigma^* : ...
0
votes
1answer
70 views

A DFA recognizing my name

How can I know if my DFA is implemented correctly? For example, I need to build a DFA, and then minimize it which will recognize my name. Language which describe my name is: L = {pustai, marius} I ...
2
votes
1answer
30 views

Describing explicitly the MyHill-Nerode classes created by a language

I want to practice proving a language is regular or not using the MyHill-Nerode theorm, but for that I need to be able to describe the classes. Here's my practice attempt: For the language ...
3
votes
3answers
61 views

generate possible inputs valid for automata

I find lots of solution where you have an Automata and a input string , you can validate whether input string is accepted by automata or not. Can we do the reverse ? I am looking for solution which ...
1
vote
1answer
135 views

Draw a graph of DFA for a regular language

I'm trying to draw a DFA graph for the regular language where every chain: ...
11
votes
1answer
161 views

The number of different regular languages

My question is: Given an alphabet $\Sigma = \{ a,b \}$, how many different regular languages are there that can be accepted by an $n$-state nondeterministic finite automaton? As an example, let us ...
7
votes
1answer
217 views

Is the reversal of a minimal DFA also minimal?

The question is pretty much in the title. Is there ever a time where some language $L$ can be accepted by a minimal DFA with $n$ states, but $L^R$, the reversal of $L$, can be accepted by a DFA with ...
6
votes
3answers
292 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
182 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
43 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
140 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
104 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
644 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
136 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
84 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
47 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
154 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
75 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
537 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
124 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
657 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
180 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
250 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
396 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
2k 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
137 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
147 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
221 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
160 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
181 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
126 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
762 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
110 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
232 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
182 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
142 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
96 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
571 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
233 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
74 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 ...
7
votes
3answers
271 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
1k 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
374 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
417 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. ...