2
votes
Empty regular expression
The empty regular expression matches one string: the empty string. That's not everything (most strings aren't the empty string) but it also isn't nothing (the empty string is a string, and the regular ...
1
vote
Languages: Prove or Disprove that $A^* = B^* \rightarrow A=B$
If $A$ and $B$ are indeed meant to be alphabets here, they would contain only symbols, and your counterexample isn't valid. In fact, if $A$ and $B$ are alphabets, the claim is true.
However, I would ...
1
vote
Exactly what is the difference between Finite Automata and Transition Graphs?
TL;DR version:
Your initial statement was accurate - I'll add some more clarity (hopefully) for people who come across this post later on:
The formal definition (from Daniel I.A. Cohen):
A transition ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
formal-languages × 2770regular-languages × 804
context-free × 763
formal-grammars × 561
automata × 432
finite-automata × 318
turing-machines × 264
pumping-lemma × 245
regular-expressions × 212
closure-properties × 204
computability × 163
pushdown-automata × 158
undecidability × 109
complexity-theory × 95
parsers × 86
proof-techniques × 70
context-sensitive × 54
algorithms × 52
terminology × 51
reference-request × 49
compilers × 47
reductions × 43
nondeterminism × 40
programming-languages × 39
semi-decidability × 30