# Tagged Questions

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

1k 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 ...
1k 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$.
175 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 =...
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 ...
233 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 ...
92 views

76 views

### Question about deterministic finite automaton (DFA) [closed]

For $n \in \mathbb N$, an "$n-$DFA" is an automaton with exactly $n$ accepting states. Let $\Sigma=\{0,1\}$. Prove that the language $\mathcal L=\{0,00,0000\}$ cannot be accepted by any $2-$DFA.
22 views

### Construction of DFA using an odd bit of language

I am working through a lecture and it constructs a DFA using the language: $$\{w\mid w\textsf{ is any string not in }(ab^+)^\ast\}$$ What does the $(ab^+)$ mean?
41 views

### Prove that if you can derive w from α in n steps, it's possible with n left-derivations as well

My university's automata theory book claims that the following claim can be proved by induction but it doesn't bother showing the proof. I've tried to prove it myself but I got stuck at the ...
20 views

### Proving this language is non context-free

How can I prove that the language $\{ab^kab^kab^k\subset \{a,b\}^* | k \geq 0\}$ is non context-free? I've tried applying the pumping lemma but can't write a proof without considering multiple ...
81 views

### How to prove that $L=${$a^p$: p is prime} isn't regular?

I tried using pumping lemma or finding infinite equivalence classes, but I didn't succeed. It's clear to me that there is no automata that accepts this language, but I just can't formally prove that ...
30 views

### proving that if a FFA accepts L=> L is a regular language

Ok, so after wasted time for nothing on this question that I asked yesterday: proving that a regular language can be accepted by a fast finite automaton Now comes the more interesting prove: ...
41 views

79 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 ...
85 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 ...
117 views

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 31 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 60 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 ... 1answer 44 views ### Showing that all regular languages are closed under reversal 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 ... 1answer 2k views ### Languages and Grammar (Finding a language) I have a trivial question (that I have actually solved, hopefully) although I am a bit curious if my result is alright. We have$N= \{S , C ,D\}$,$T=\{c, d\}$and$P = \{S \to Dc, D \to Dd, D \to Cd,...
195 views

I need to find DFA (or NFA, $\epsilon$-NFA, it's not improtant (I know how to convert between them)) that accept all strings of $0$'s and $1$'s such that every block of five consecutive symbols ...
77 views

### Why is this the $L(M)$ of this DFA?

Why is this the $L(M)$ of this DFA? Can someone please explain it? I am new to this course. When I tried alone answering the question of "What is special about the words that get accepted by this DFA?"...
212 views

### Constructing a parallel composition from a given transition system and automaton

I am looking at an exercise, where it asks me to construct a parallel composition from a given transition system and an automaton. The transition system looks like this: and the automaton (with ...