# Tagged Questions

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

234 views

### The halting problem for tapes that are or are not completely blank

Is it possible to construct a Turing machine that halts only if the tape is not completely blank? Also, is it possible to construct one to halt if the tape is completely blank? Intuitively, I think ...
240 views

### NFA for $(ab|a)^{*}$ using only 2 states

In Introduction to the Theory of Computation by Michael Sipser, there's an example which shows how to convert the regular expression $(ab|a)^{*}$ into an NFA. The "standard" method results in 8 ...
108 views

### Grammar outside the Chomsky Hierarchy

This grammar describes a language that may fall outside the Chomsky Hierarchy (CH): \begin{array}{l} S \to abAbba \\ A \to abA \mid bbaB \\ B \to aab \\ \lambda \to Aab \mid aB \\ \end{array} Going ...
76 views

### Infinite regular languages

There is a formal proof for the following sentence? For every 2 languages $A,B$, we write A@B if A subset of B and B\A infinite. Prove that if $A,B$ regular languages and A@b, than exists regular ...
35 views

### Construct a deterministic finite automation

The question asks to: construct a DFA which accepts exactly $\frac{n(n-1)(n-2)}{6} + \frac{n(n-1)}{2}+1$ many members of $\{0, 1\}^n$ for every n. I have no idea where to start to constructing the ...
2k views

### Concatenation of 2 finite Automata

I have some problems understanding the algorithm of concatenation of two NFAs. For example: How to concatenate A1 and A2? A1: ...
220 views

### Prove that any finite set of words is regular. How many states is sufficient for a single word $w_1…w_m$?

DFA Prove that any finite set of words is regular. How many states is sufficient for a single word $w_1...w_m$? For part 2, wouldn't it require M states if the word length is M?
125 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 ...
432 views

### A regular expression for the words that don't contain the sequence $ab$ over $\{a,b,c\}$

The following is an exercise in a book I am reading: Let $\Sigma=\{a,b,c\}$, define $L$ to be the language of all words over $\Sigma$ that do not contain $ab$ as a sub-word. Find a regular ...
37 views

### Regular Expression to a Deterministic Finite Automata with Kleene Closure

I'm asked to make a DFA for the following: $\Sigma = \{a, b \}$ and $\{$ w | w does not contain the string ab $\}$. My first approach was to convert this into a regular expression by taking the ...
38 views

### How to design a finite state automaton that recognises the languages like $1^n 0^n$

The question goes like this: Design a finite state automaton that accepts binary strings with at least two $0$s and at most two $1$s. I can easily design an NFA which accepts at least two $0$s OR at ...
51 views

### Why |w|>=m in pumping lemma?

If L is a regular language, then there exists a constant n (which depends on L) such that ...
47 views

I have this assignment and I have to prove that $$(b+aa^* b)+(b+aa^* b)(a+ba^* b)^* (a+ba^* b) = a^* b(a+ba^* a)b^*$$ How do I prove this? What I have is this: \begin{align} \text{LHS} ... 3answers 53 views ### Show that a language is regular Show that language B is regular:B = \left\{1^ky\mid y\in \{0,1\}^*\right\} $$y contains \ge k symbols 1 So I try in following way - I'll draw DFA: What about my solution? Is it good? 2answers 39 views ### Did I find the right expression for the regular language for this FSA? I have the following FSA, and the regular language that I found for it: Is this language correct? It doesn't match the solution in the book, but my teacher says there can be multiple equally ... 2answers 31 views ### FSM to be regular with atleast two 0's and at most two 1's Is it possible to construct a FSM to prove that the set X is regular, where$$ X = \{s \in \{0,1\}^* \mid \text{$s$ contains at least two $0$'s and at most two $1$'s}\}\ ? $$1answer 43 views ### Can someone explain to me how this is a proof? I honestly don't understand how this proves anything. 2answers 48 views ### Closed regular languages Are regular languages closed under the following construction? f(L) = \{w \mid w \in L and for all prefixes x of w it holds that x \notin L \} 1answer 31 views ### Subset of regular languages Assume L_1 and L_2 two regular languages, and L_1\subseteq L\subseteq L_2. Does this imply that L is a regular language? Thanks in advance. 2answers 71 views ### New automaton that runs two others step by step? If I have two automatons for two languages (M_1, M_2, L_1,L_2 respectively), what would be the procedure to mix them by defining a new automaton such that the new automaton would accept the words ... 2answers 167 views ### Whether L=\{(a^m,a^n)\}^* is regular or not? I am condidering the automatic structure for Baumslag-Solitar semigroups. And I have a question. For any m,n \in Z, whether the set L=\{(a^m,a^n)\}^* is regular or not. Here a set is regular means ... 1answer 817 views ### How to prove CYK algorithm has O(n^3) running time I have a final coming up in few days, and the professor mentioned the CYK algorithm. I want to be prepared for the final. I'm trying to find out how to prove the algorithm has worst case running time ... 2answers 848 views ### Showing that a language is regular - Pushdown Automaton So what I have to prove is that L is regular given that the stack of PDA for L never grows beyond n entries on any input, and in this case n=200. 2answers 153 views ### Solve right linear set equations Trying to solve this set of equations. I'm feeling like I'm making it so complicated. Of course + is union. Am I on the right track? A = 0B + 1D B = 0C + 1A C = 0A + 1B + λ D = OD + 1C + λ A ... 2answers 1k views ### Can _any_ NFA be converted to a DFA? I was wondering if for every NFA there exists an equivalent DFA? I think the answer is yes. How would one prove it? Since I'm just starting up learning about Automata I'm not confused about this and ... 2answers 225 views ### Pushdown Automaton Can someone help me construct a pushdown automaton to recognize the following regular expression representing the language (a^3+a^5)* using as few states as possible? How can this be done using a ... 1answer 86 views ### Show that a^k w b^k when |w|_a is divisible by 3 is not regular I want to show that L = \{ a^k w b^k \mid k \geq 0, w \in \{a,b\}^*, |w|_a \text{is divisible by } 3 \} is not regular. I tried to use Pumping lemma as follows: Let p be pumping length. a^pb^p ... 1answer 50 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 ? 1answer 200 views ### Finite Automata, basic question with semigroups If we use the notation where when we say:$$M = M(G)$$We mean to say that M is a automata with states and alphabet elements of G. From here, I am posed this question (Abstract Algebra by ... 1answer 182 views ### CFG pumping lemma I can't figure out how to prove this is a non CFG. \{xy : x, y \in \{a,b\}^*, n_a(x) = n_a(y), n_b(x) = n_b(y) \}, Where the number of a's in x = number of a's in y and number of b's in x = to the ... 3answers 29 views ### If L_1 and L_2 are regular then L_1 \cup\;L_2\; = L is regular. Is the converse true? The following is an answer I found to the question. For instance, \sum^* is a regular language; but it can be decomposed into two languages L_1= \{0^i1^i,\;i\ge0\} and L_2 = ... 1answer 60 views ### recurrence relation of a language I am looking at the following: Consider a language X which consists of all bitstrings with no more than 2 consecutive zeros (represented by the above automaton). Next consider a sequence s_n ... 1answer 35 views ### Alphabets of Turing Machine I'm not completely sure about equivalence of two definitions of Turing machine. The first one states that Turing machine has a finite alphabet \Sigma, set of states and some rules. Turing machine ... 1answer 44 views ### How n (1+b) is not prime? Here is the complete proof taken from this link How do I convince myself that n(1+b) is not prime when b>=1? Here is what I did: if n is 3 and b is 3. Then ... 2answers 50 views ### Proving that L := \{a^n\mid\exists k \geq 0\ n = k^3\} is not a regular language I'm having trouble using the pumping lemma to prove this language L := \{a^n\mid\exists k \geq 0\ n = k^3\} is not regular. Assume L is regular. Thus there is a DFA M for it. Choose m as the ... 1answer 230 views ### Why are Recursively enumerable languages closed under intersection? when Recursively enumerable sets are not closed under complement ,then how come they are closed under intersection because the definition of intersection comes as L1 intersection L2= complement(L1' ... 1answer 46 views ### Write grammar for given language I'm trying to write a grammar for the language below:$$(a+b)^*−\{𝑤𝑤𝑤 ∶ 𝑤\in\{a,b\}^*\}$$could anyone help me? 2answers 88 views ### What the way studying math to automata theory Good day everyone. I need to know automata theory. Can you advice me the best way to study math? What themes will I need to know to understand automata theory. What a sequence of study? What level ... 1answer 12 views ### Find a state machine or a regex that accept the following language description The alphabet of the language L is {a, b} and there has to be an even number of both a's and b's but no other restrictions apply. I've been at this for over an hour, drawing state machines that lead ... 1answer 92 views ### NP^{PP} vs. PP^{NP}, which one subsumes the other? I understand why P with an NP oracle (P^{NP}) subsumes NP: because it contains co-NP. But how about NP with a P oracle? Can it be any different from NP? (I'm guessing they are the same otherwise ... 2answers 61 views ### NFA for L = \{ w \in \{a,b,c\}^* : \text{at least one symbol appears only once in }w \} Write an NFA to recognize the language$$L = \{ w \in \{a,b,c\}^* : \text{at least one symbol appears only once in }w \}.$$I'm not quite sure how to do this question. I don't know how to keep ... 2answers 66 views ### Is this DFA correct? I am reviewing. I need to write a DFA that accepts a string w such that bab is not a substring. Is there any error. Also, any guideline or tips? Since it's a DFA I don't make more than 2 ... 2answers 114 views ### Euclid's Proof that there are an infinite number of primes I'm trying to clarify my understanding of decidability of a language. The following question is totally made up by me so I hope it makes sense. Let L = \{A: A \text{ is an algorithm that can ... 1answer 28 views ### How to prove the following related with regular languages How can we prove the following. If$$\sum$$is any alphabet and L is any language$$L \subset \sum*$$Then L*L* = L* ? 1answer 49 views ### Particular Problem for Context Free Grammars Consider the context-free-grammar G defined by productions:$$ S \rightarrow aS\,|\,Sb\,|\,a\,| b  Prove by induction on the string length that no string in $L(G)$ has $ba$ as a substring. I ...
I'm trying to show that $L^{reverse} = \{w^{reverse}:w \in L\}$ is a regular language. The first argument I can come up with is simply: if we have an NFA for $L$, then an NFA for $L^{reverse}$ can be ...