# Tagged Questions

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

36 views

### Turing Machine Diagram, one Solved Problem ?!

The following Diagram Gets binary number $x$ and produce $x+1$. complete it: the book solution is says first line is the answer. any hint or idea for completing this TM?
32 views

158 views

### How can a Moore machine be converted into an equivalent Mealy machine and vice versa?

Moore machine is a finite-state machine whose output values are determined by its current state only. Mealy machine is a finite-state machine whose output values are determined both by its current ...
126 views

### Designing a Turing machine for $a^n$ $b^{2n}$ $a^n$

I am new to theory of automata, and i have a little knowledge of designing a turing machine, I am stuck in this question which is given to us as an assignment, $\{$$a^n b^{2n} a^n : n\geq0$$\}$...
3k views

1k views

77 views

### Understanding Turing Machines: Recognizable and Decidable langauges

I've searched tons of resources and while conceptually I understand the turing machine itself and what it does- I'm a bit stuck on Turing Recognizable and Turing Decidable languages and I'm not sure ...
38 views

### Writing a regular expertion for the language $L=\{0^n1^m \mid n\equiv m\pmod 2\}$

I need to write a regular expertion for the language of all the binary words that contains continuum of even number of zeros and after that even number of ones or odd number of zeros and after that ...
103 views

### Regular expression for string's of a's and b's beginning with b and not having two consecutive a's

Question: Write a regular expression for the following language: "All strings of a's and b's in ∑* beginning with b and not having two consecutive a's. A textbook says the answer is (b+ba)*. Shouldn'...
46 views

### Pumping Lemma Proof for non-regular languages

Okay, so this is a confusing and abstract topic. I'm having some trouble proving a language is not regular using the Pumping Lemma. Suppose I have: $L = \{ a^ncb^n | n >0\}$ I know for a fact ...
43 views

### Why is this language not regular?

I am studying Automata using the Coursera course created by Jeff Ullman. On slide 36 of this presentation: http://spark-public.s3.amazonaws.com/automata/slides/3_fa2.pdf it says that the language is ...
I couldn't figure out how to proceed with this question. Preparing for the finals, can someone explain how to do this step by step? Design a TM, write low level transitions for $\{a^i b^j :i ≤ j ≤ ... 1answer 38 views ### Finding regular expressions for which a given Turing machine halts and accepts, halts and rejects, and diverges. Consider the Turing machine M = (Q,Σ,Γ,δ,q,F) F = {t} Q = {q,r,s,t,v,x} Σ = {a,b,c} Γ = {B,a,b,c} δ = [q,a,q,a,R] [q,b,q,b,R] [q,c,v,b,R] [q,B,r,B,L] [r,a,s,B,L] [r,b,s,B,L] [r,c,s,B,L] [s,a,x,a,... 0answers 77 views ### Trouble with induction on the length of a word In the accepted solution of the question If L is regular, prove that$\sqrt{L}=\{w:ww\in L\}$is regular the answerer made the claim that "What's left is to show that$δ ′ (q_{0}' ,w)=h$, which can ... 0answers 284 views ### nth-root of continued fraction with Raney transducers There are some algorithms for doing basic arithmetic by using regular continued fraction expansions. These algorithms are mainly due to Gosper (1972) and Raney (1973). These two approaches use (bi)... 1answer 136 views ### Show that the function floor-log is primitive recursive I have been stuck on this problem for a while and I was hoping someone could help me with it. This is for my computer science automata and formal languages class. Given an integer$b$greater than or ... 0answers 45 views ### show that language is regular Let$B_n = \{a^k\ |\text{ where } k\text{ is a multiple of } n\}$. Show that for each$n\ge 1$the$B_n$language is regular. My proposition of solution: What about it ? 1answer 58 views ### Intersection of context-free language and its reversal I know that intersection of two context-free languages is not always context-free and the following problem: Given two context-free languages A and B, is$A \bigcap B \neq \emptyset$? is ... 0answers 42 views ### Size of automata or regular expressions avoiding cross patterns Let$\Sigma$be an alphabet of finite size$k$, and$n$some integer. I am interested in the language of words of size$n$that do not contain$abab$as a subword, for any pair$(a,b) \in \Sigma$(I ... 1answer 122 views ### Is it possible to make a PDA for$\{ ww : w \in \{ 0,1 \}^* \}$? Consider the language$L = \{ ww : w \in \{ 1,0 \}^* \}$. I know it's easy to make a PDA for$\{ w w^\text{R} : w \in \{ 0,1 \}^* \}$where$w^{\text{R}}$is the reverse of$w$, but I can't think of ... 1answer 239 views ### Pumping Lemma for regular languages proof template http://www.cs.uiuc.edu/class/fa06/cs273/Lectures/pumping-lemma/pumping-lemma.html So, I went to that site and it says:$w = xyz|xy| \leq p|y| \geq 1$for all$i$,$xy^iz$is in$L$.... 1answer 90 views ### Context free grammar for language I'm learning how to generate context-free grammar for a language.$L=\{{a}^i {b}^j {c}^k\, |\,i=j\lor j=k$Here is how I tried ... 0answers 77 views ### halting problem Prove that it is undecidable for the halting problem of a deterministic Turing machine which accepts nonrecursive language or in-other-words: let's say we have a deterministic Turing machine which ... 0answers 161 views ### Blanks in the Tape of a Turing Machine I used to have a lot of trouble with Turing Machines, primarily because I thought that in-between input symbols on the tape, one could have an arbitrary number of blanks, so every input would need to ... 1answer 136 views ### Build regular expression from language I have the following language: L = {w$\in${a,b}* | aa is not part of w}. I have to construct a regular grammar from this language and I thought about first finding the regular expression from the ... 0answers 77 views ### Turing Machines Suppose that$\Sigma$is a finite set and that$L_1$,$L_2$and$L_3$are Turing acceptable subsets of$\Sigma^*$that satisfy the following properties:$L_1 \cup L_2 \cup L_3 = \Sigma^*$;$L_1 \cap ...
I have the following problem of converting CFG to CNF:  \begin{aligned} S \Rightarrow\,& bA \mid aB\\ A \Rightarrow\,& bAA \mid as \mid a\\ B \Rightarrow\,& BB\mid bs\mid b \...