user avatar
user avatar
user avatar
Oleg Dats
  • Member for 3 years, 3 months
  • Last seen more than a month ago
3 votes
3 answers
126 views

Is it possible to have high compression but low predictability?

2 votes
1 answer
117 views

Is it possible to constract Moore or Mealy machine with a different size of input and output?

2 votes
1 answer
102 views

What doest it mean: "computer is an intelligence amplifier"?

2 votes
2 answers
46 views

Single-tape $o(n\log n)$ Turing machines and nonregular languages

1 vote
4 answers
1k views

What is the name of the following binary encoding?

1 vote
0 answers
33 views

How to prove existance and construct finite-state transducer between two different FSM?

1 vote
2 answers
51 views

Can you have simple unit tests for complicated function? [closed]

1 vote
0 answers
48 views

What is the connection between finite automata and logic (sequential calculus)?

0 votes
1 answer
91 views

Disambiguating grammar for Dyck language

0 votes
0 answers
30 views

How to count the number of nodes for a tree generated by context free grammar derivation?

0 votes
1 answer
52 views

Is there a version of the boolean satisfiability problem that has NC complexity?

0 votes
1 answer
79 views

How to define enumeration of the set of finite state machines?

0 votes
0 answers
50 views

How to reduce Checkers to P and NP-complete?

0 votes
1 answer
85 views

An algorithm to check if two DFA are disjoint

0 votes
0 answers
21 views

Does the assertion that most Boolean functions require exponential-sized circuits implies that most languages are at least NP?

-1 votes
1 answer
41 views

Prove that given 2 regular expressions represent the same language