Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

learn more… | top users | synonyms

1
vote
1answer
806 views

Proving regular expressions to be equivalent

I'm trying to prove that two regular expressions are equivalent. I mean prove in the rigorous sense of the word (i.e. this is a legit proof). The process is to show that R1 is a subset of R2, and ...
0
votes
1answer
245 views

Complementary language of a context free grammar

First post on Mathematics ;) I'm stucked with a problem related to automata theory / formal grammars. The problem ask the student to design a Pushdown automaton that accepts the complementary ...
2
votes
1answer
211 views

Generating all words in a language from CFG

I have a non-ambiguous context-free grammar. Is there some standard algorithm to create list of all the words in the language the CFG defines? This can be done with an abvious brute-force search by ...
4
votes
1answer
77 views

Enhancing the monoid structure over a finite alphabet to prove Arden's rule

Suppose you have a finite-state, deterministic automaton, that you wish to convert to a regular expression. A common method, perhaps easier to apply by hand that Yamada's algorithm, is to reduce the ...
3
votes
1answer
2k views

How to show that $ALL_{DFA}$ is in P

How can I show that $ALL_{DFA}$ is in P ? $ALL_{DFA} = \{ \langle A \rangle \mid A \text{ is a DFA and } L(A) = \Sigma^* \}$
1
vote
2answers
265 views

Is this DFA correct

I'm supposed to construct a DFA which accepts { w | w is a word except 'aa' and 'aaa' } Is this the correct solution? The thick line state is supposed to be the end state. EDIT Sry, somehow ...
1
vote
2answers
3k views

Understanding $\epsilon$ transitions in a finite state automaton

I am trying to understand how $\epsilon$ transitions work. From what I've read, when you "go" to a state S that has arrows pointing outwards with $\epsilon$'s in it, you automatically go to those ...
2
votes
1answer
797 views

Nondeterministic Finite Automata to Deterministic Finite Automata?

I am unfamiliar with the general process of converting NFA to DFA. I have general understanding of the theory, but I don't have the method established. Please help explain the process required to ...
2
votes
5answers
5k views

Program for working with DFA/NFA/PDA?

I'm looking for a program or utility to help construct DFA/NFA/PDA etc. and the like. The main reason I'm interested in this, is because I want to be able to move the various states around without ...