9
votes
1answer
134 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 ...
5
votes
2answers
99 views

What is the field studying the search and generation of computer programs?

This Github repo hosts a very cool project where the creator is able to, give an integer sequence, predict the most likely next values by searching the smallest/simplest programs that output that ...
6
votes
2answers
95 views

How to find the minimal description for an array?

The following array occupies 10000 slots in memory: a = [0,1,2,3,4,5,6,7,8,9,10,...,10000] But one could easily represent the same array as: ...
7
votes
0answers
86 views

Test whether two languages are equal, when give in algebraic form

This sub-problem is motivated by Algorithm to test whether a language is regular. Suppose we have two languages $L_1,L_2$ that are expressed in "algebraic" form, as formalized below. I want to ...
8
votes
1answer
231 views

Algorithm to test whether a language is regular

Is there an algorithm/systematic procedure to test whether a language is regular? In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n : n \in ...
9
votes
0answers
163 views

Algorithm to test whether a language is context-free

Is there an algorithm/systematic procedure to test whether a language is context-free? In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in ...
10
votes
1answer
174 views

How do I find the shortest representation for a subset of a powerset?

I'm looking for an efficient algorithm for the following problem or a proof of NP-hardness. Let $\Sigma$ be a set and $A\subseteq\mathcal{P}(\Sigma)$ a set of subsets of $\Sigma$. Find a sequence ...
0
votes
2answers
209 views

Fundamental algorithms in formal language-automata theory [closed]

I'm willing to take a course in formal languages and automata theory , where we will explore side by side a functional programming language to implement the different algorithms we will encounter ...
12
votes
1answer
590 views

What is the difference between an algorithm, a language and a problem?

It seems that on this site, people will often correct others for confusing "algorithms" and "problems." What are the difference between these? How do I know when I should be considering algorithms and ...
-2
votes
2answers
330 views

How to do Big 'O' notations [duplicate]

How can I solve $\mathcal{O}$-notations without using Java or any other programming language? I only want to use pen and paper.
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 ...
3
votes
2answers
231 views

What type of formal notation is being used here to represent functional algorithms?

Interested in learning more about algorithm design in functional programming, I picked up Andrew Bird's Pearls of Functional Algorithm Design. I have experience with a number of programming ...
3
votes
1answer
567 views

Evaluation of reverse Polish notation

We only consider the reverse Polish notation as an arithmetic expression. Formally, RNP is a sequence consisted of numbers and arithmetic operators: $+,-,*,/$, and its syntax is: ...
3
votes
2answers
197 views

Construct a context-free grammar for a given set of words

I have seen a few years back a nice and simple algorithm that, given a (finite) set of words in some alphabet, builds a context-free grammar for a language including these words and in some sense ...
2
votes
1answer
55 views

How does this algorithm for verifying if a string is $0^n1^n$ work?

I have found an efficient algorithm for verifying if a string $\omega$ is of the form $0^n1^n$, where $n \in \mathbb{N}$. Scan across $\omega$. If a 1 appears before a 0, then reject. Repeat so long ...
6
votes
1answer
191 views

Represent string as concatenations

If $S_1,S_2$ are set of strings, then $S_1S_2 = \{s_1s_2|s_1\in S_1, s_2\in S_2\}$. $S^0=\{\epsilon\}$, $\epsilon$ is the empty string. $S^n = S^{n-1}S$. Two related problems about represent string ...
4
votes
1answer
276 views

Time complexity of an enumeration of SUBSET SUM instances

An instance of the SUBSET SUM problem (given $y$ and $A = \{x_1,...,x_n\}$ is there a non-empty subset of $A$ whose sum is $y$) can be represented on a one-tape Turing Machine with a list of comma ...
26
votes
4answers
18k 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 ...
10
votes
3answers
702 views

How to convert an NFA with overlapping cycles into a regular expression?

If I understand correctly, NFA have the same expressive power as regular expressions. Often, reading off equivalent regular expressions from NFA is easy: you translate cycles to stars, junctions as ...