1
vote
is {w in {0,1}* | #0(w) = #1(w)} a regular language?
No, this language isn't regular. @MJD has a great intuitive explanation for this in the comments: determining whether a string is in this language requires tracking the relative numbers of 0s and 1s, ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
computer-science × 5178algorithms × 810
discrete-mathematics × 665
computational-complexity × 529
logic × 407
graph-theory × 380
computability × 369
automata × 347
formal-languages × 301
asymptotics × 298
combinatorics × 292
turing-machines × 201
regular-language × 186
context-free-grammar × 169
linear-algebra × 158
computational-mathematics × 158
recurrence-relations × 125
probability × 123
np-complete × 120
number-theory × 118
optimization × 103
recursion × 99
geometry × 91
numerical-methods × 90
reference-request × 88