# Tagged Questions

41 views

### Turing machine true/false questions

There is a non-regular language that is recognized by a Turing Machine. I believe the answer to this is true, because Turing machines can "count" computations and ...
49 views

### Turing machine for $\min(x,y)$ [closed]

How would we pictorially construct a Turing machine to compute $\min(x,y)$, the smaller of $x$ and $y$?
118 views

### Regular expression and DFA/NFA questions

If a language L is generated by a regular expression, then L is recognized by a DFA. I think this is true, because regular expressions describe regular languages, those of which are exactly ...
44 views

### Reduction between two languages and a common one

My question is as following : Let $A$ and $B$ be some languages, there exist a language $C$ such that $A\le C$ and $B\le C$, where "$\le$" means "reducible to", so $A\le C$ means there is a mapping ...
29 views

### Determining a language with a Turing Machine

How can I build a Turing Machine that determines the following language? $$L_{E - DFA} = \{\langle A \rangle | \text{A is a DFA and L(A) = \varnothing}\}$$ Thanks alot
20 views

### If $s \geq 3$, $3$ divides $s$, and $t = s/3$, then $t+1 < s$.

I am using the pumping lemma to prove a language is not regular, and would like to assert what I have stated in the title of the question to complete my proof. That is, if $s \geq 3$, $3$ divides $s$, ...
43 views

### Theory of Automata concepts

I just started taking Theory of Automata and I'm having a hard time understanding some of the concepts. It's been only a week and the following questions are my homework. I'm not asking you to do my ...
45 views

### Finding regular expressions

I'm given the DFA shown below and need to find regular expressions for the following languages: $L_{1,2}^0, L_{2,1}^6, L_{2,5}^4, L_{2,3}^5, L_{1,3}^5$. The language $L_{p,q}^r$ is defined as ...
45 views

### One counter automata

A one-counter automaton $M = (Q, S, \Gamma, t, s, A)$ is a pushdown automaton where the stack alphabet $\Gamma$ contains just two symbols $\#$ and $g$. The symbol $\#$ is initially written on the ...
40 views

1k views

### My Moore and Mealy machines look the same. Why?

For university I have to construct equivalent Mealy and Moore machines that solve certain problems. But I am confused, as my Moore and Mealy machines turn out to have exactly the same nodes, just with ...
76 views

### L is a context free language over {0, 1}, prove, disprove:

cont... L is a context free language over {0, 1}, prove, disprove: L1 is a CFL over {a, b}, where L1 is the language of all words from L, that 0 is converted to a and 1 is converted to bba. Thanks ...
559 views

### How to prove by pumping lemma these languages are not regular?

$L_1 = (a^k * b^r \mid k \neq r^2)$ $L_2 = (a ^{\sum_i ^n t} \mid n > 0 )$
83 views

### Prove min(L) = all words in L that they don't have any prefix of themselves in L

We define the minimal words language of $L, \min(L)$, to be the language of all words in $L$ that don't have any prefix in $L$. Assume $L$ is regular language. I need to prove by building an ...
97 views

### showing that a regular language is regular after taking a letter off or after adding letters

I'll be happy to recieve help with this one: Given the regular language $L$ defined over alphabet $\{a,b\}$, show that the following languages are also regular: $\{xy\mid xay\in L\}$ ...
539 views

### Formal proof of the concatenation of two regular languages automaton

During an exercise for college, given two NFA's, $A_1\text{ and }A_2$ that accept the languages $L_1\text{ and }L_2$, I've built a NFA, $M$ that accepts the language $L_1*L_2$ (concatenation). The ...
77 views

### Is the language $\{i|f(i)=1\}$ recursive, function $f$ is described further inside. [duplicate]

Possible Duplicate: Show $f$ is primitive recursive, where $f(n) = 1$ if the decimal expansion of $\pi$ contains $n$ consecutive $5$'s $$L = \{i\mid f(i)=1\}$$ $f(i)$ equals $1$ if ...
2k views

### Design Push Down Automata to accept palindrome by empty stack

I'm trying to make a PDA that accepts the language w001(rev w) | w = {0,1}* by empty stack, where rev w means the reverse of w. (Stack symbol = #) I've come up with this so far, but I don't know how ...
98 views

### Existence of NFA for this language

I'm given a task to find (and prove) such language $L$ in the alphabet $\Sigma = \{a,b\}$ with all words less than $1000$ in length, for which any DFA/NFA will have more than $10^{10}$ of states. For ...
91 views

### Conditions for: $xy=zw$ and $yx=wz$

Let $x,y,z,w$ be finite strings. Find the necessary and sufficient conditions for the following two equations to hold simultaneously: $$xy=zw$$ and $$yx=wz$$ Automata Theory is new to me and i am ...
811 views

### If L is regular, so is $L-\{λ\}$?

A language is regular, by definition, if you can create a DFA for it. Then I need to prove that if $L$ is regular, then so is $L-\{\lambda\}$ for any $\lambda\in L$. Any ideas?
48 views

### what is the effect of adding another stack to a PDA

does it increase the power of a push down automata? or does it have no effect on the power of the PDA ?