# Tagged Questions

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

190 views

### Construct a deterministic finite state automaton

Construct a deterministic finite-state automaton that recognizes the set of all bit strings that end with 10. This is what I drew. Not sure if its correct. State 2 is the final state. Am I missing ...
36 views

### Let $LOOP_{TM}$ be descriptor language of all touring machines that won't halt for any input. Show reduction of $HALT_{TM}$ to $LOOP_{TM}$

Question from Homework that I'm having difficult to answer on: Let $LOOP_{TM} = \{\langle M\rangle \mid \text{M is a TM that does not halt on any input w}\}$ Let $LOOP_{TM}$ be descriptor ...
41 views

### Is $L = \{0^{i}1^{i}0^{j}1^{i} | i, j > 0\}$ a context free language?

Is the following argument correct? $L = (A \circ B) \cap C$ where, $A = \{0^{i}1^{i}$ $|$ $i > 0\}$ $B = \{0^{j}1^{i}$ $|$ $i, j > 0\}$ $C = \{0^{i}1^{j}0^{k}1^{i}$ $|$ $i, j, k > 0\}$ We ...
79 views

### Where is my mistake in this DFA minimization?

I'm currently having trouble minimizing my DFA. I have the following graph: (ignore the numbers after ":") Using the table minimization method I reached: (x is distinguishable, O is non-...
65 views

49 views

### Language requiring a DFA with a certain number of states to implement

For any function $f\colon\{0,1\}^n\to\{0,1\}$, define a language $S_f = \{(b_1,b_2,\ldots ,b_n)\in\{0,1\}^n : f(b_1,b_2,\ldots ,b_n) = 1\}$. So all words in the langugage has same length $n$. I have ...
360 views

### DFA for Boolean Formula

Let $f\left( b_{1}, \dots , b_{n} \right)$ be a boolean function. Define $S_{f} = \{\left( b_{1}, \dots , b_{n} \right): f\left( b_{1}, \dots , b_{n} \right)=1; b_{i} \in \{0,1\}, 1\leq i \leq n \}$ ...
123 views

### Difference between $(a|b)^\ast$ and $a^\ast b^\ast$?
What is the difference between $(a|b)^\ast$ and $a^\ast b^\ast$? Can you show more examples of Kleene star and patterns and explain a little bit? I've searched so many sites in Google, but it returns ...
$L_1=\{a^nb^mc^nd^m \mid m,n >0\}$ $L_2=\{a^nb^mc^md^n \mid m,n >0 \}$ $L_3=\{a^mb^n \mid m+n\text{ is a prime number}\}$ $L_4=\{a^mb^n \mid n=m^2\}$ \$L_5=\big\{ww^R\#ww^R \mid w \in \{a,b\}^* \...