# Tagged Questions

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

880 views

### If $L$ is regular, prove that $\sqrt{L}=\left\{ w : ww\in L\right\}$ is regular

Let $L$ be a regular language. Prove that $\sqrt{L}:=\left\{ w : ww\in L\right\}$ is also a regular language. I suppose I need to modify state machine for $L$ to accept $\sqrt{L}$, but I've been ...
46k views

### Difference between NFA and DFA

In very simple terms please, all resources I'm finding are talking about tuples and stuff and I just need a simple explanation that I can remember easily because I keep getting them mixed up.
12k views

138 views

### Formal Languages - Regular Expression

I've been battling the following two questions for more than a day today. Write a regular expression (comprised of {a, b}) that contain at least two b and do not contain abb. Write a regular ...
351 views

5k views

### Finite automaton that recognizes the empty language $\emptyset$

Since the language $L = \emptyset$ is regular, there must be a finite automaton that recognizes it. However, I'm not exactly sure how one would be constructed. I feel like the answer is trivial. ...
177 views

### Can you draw the e-NFA from the following definition?

I am trying to understand the solution, because I think I got it completely wrong. I wrote we could take the initial DFA and replace the normal transitions with epsilon transition except for all ...
91 views

### NFA from grammar productions

Based on this grammar: \begin{align} G = (\{S,A,B\}, \{a,b, c\}, S, P) \end{align} \begin{matrix} \\P: \\S → abaS | cA \\A → bA | cB | aa \\B → bB | cA | bb \end{matrix} I created this NFA: I'...
148 views

### Two elementary question on automaton and language

1.What is the definition for a semigroup(or monoid) recognizing a set of words(or language)?2.Are recognizable,rational and regular equivalent to each other with respect to a language? PS:The reason ...
1k views

### Turing Machine Variation

Hi i'm trying to figure out this question: Give a formal definition of multihead-multitape Turing machine. Then show how such a machine can be simulated by a standard Turing machine Can someone ...
39 views

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

I need to find and to prove (by the pumping lemma or by building a grammar) if $L=\{o^{i}1^{i}o^{j}1^{i} | i,j>0\}$ is a context free language. I would like to get some help. thanks!
195 views

### How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j c^k| j \gt i+k\}$?

How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j c^k| j \gt i+k\}$? I don't have much idea how to approach this one. Could some help me to understand how to approach these ...
301 views

### Greibach normal form conversion

I'm trying to convert this into GNF: $S \rightarrow ASaa | bab$ $A \rightarrow Ba | bAB$ $B \rightarrow abba$ So I'm getting this, but I'm not sure understanding and applying correctly the concept ...
469 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 ...
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 ...
136 views

### Pumping Lemma to show a language is not regular

Let $\Sigma = \{a, b\}$. Use the Pumping Lemma to show that $\mathcal L = \{ a^pab^q: p < q \}$ is not regular. Not sure how to apply PL here, if someone can give some direction.
178 views

### How to design a Context-Free Grammar and Pushdown Automaton for the following language:

How would you design a context-free grammar for the following language? $\{p^n \ r^m \ p \ \ b^{m+n} \ \ r^2 ∣ m,n\geq 0\}$ Derive a Pushdown Automaton that accepts the same language as the CFG. ...
120 views

### Describe and count the set of sequences containing $20$ or $02$

Let $X = \{ 0,1,2 \}$ be a ternary alphabet and denote by $X^*$ the set of finite sequences (i.e. strings) with three symbols. For $w \in X^*$ with $n$ the length of $w$ and $w = w_1 w_2 \cdots w_n$ ...
304 views

### Generating all words in a language from CFG

I have a non-ambiguous context-free grammar. Is there some standard algorithm to create list of all the words in the language the CFG defines? This can be done with an abvious brute-force search by ...
76 views

### Is regularity is preserved under reversal?

When talking about languages and regular languages. Can I say that reversal preserved regularity since if the language L is regular, we can generate it by right linear grammar. Therefore, the ...
104 views

### Prove that $\{ww^R\#ww^R\}$ is not context free

I need to prove that $L = \{ww^R\#ww^R \; | \; w \text{ is in } \{a,b\}^*\}$ is not context free. I have tried using the pumping lemma for this. For $w=a^pb^pb^pa^p\#a^pb^pb^pa^p$. I have two cases ...
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 ...
704 views

### NFA to DFA conversion, half the power set

Is there a way to tell when a NFA will use at least half the power set when converted to a DFA. I tried to create a few examples, but i just can't see a pattern that would say whether an NFA will use ...
24 views

### Parser for reversed language

Language $L$ is specyfied by grammar : $(\{S,A,B\},\{c,d\},S,\{S \rightarrow SA, A \rightarrow Bc | \epsilon, B \rightarrow d\})$. My task is to construct LR(1) parsing table for language $L^R$ (with,...
37 views

Is there any formal and elegant way of finding the language of a finite automaton? For example, It's trivial that the language accepted by the following diagram of the automaton $A$ is $L(A) = (a ... 1answer 69 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$... 2answers 171 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 63 views ### Working with the word w⋅y, while given the word y⋅w$L$is a regular language. I am given$F(L)$such that $$F(L)= \{wy \mid yw\in L\}$$ I need to prove that if$L$belongs to$L_\text{dfa}$,$F(L)$also belongs to$L_\text{dfa}$. I am having a hard ... 2answers 40 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 41 views ### Regular expression for language containing all strings that start and end with different symbols ques - Regular expression for language containing all strings that start and end with different symbols i just went through some examples where the RE for above question is ... 2answers 69 views ### Determine whether$L=\{w:|w|_a=2^n+273\text{ for }n\in \mathbb{N}\}$is regular. Given the alphabet$\Sigma=\{a, b\}$and for the next Language$L=\{w:|w|_a=2^n+273\text{ for }n\in \mathbb{N}\}$determine whether the language is regular. Firstly, I think this language is regular. ... 1answer 112 views ### How can a DFA corresponding to an NFA have a transition that the original NFA does not? First sorry for the poor pictures, but I think they are ok enough to get the point across. I would like to see the steps involved to convert this NFA to a DFA using the method explained in this ... 2answers 197 views ### Designing a deterministic finite automata How would I go about designing a deterministic finite automata to recognize the language L = {λ, ab, abab, ababab, . . . } consisting of strings that start with ‘a’, end with ‘b’, and alternate in ... 1answer 41 views ### Proving that the language$\mathscr L$is non regular using the pumping lemma I need to prove that the language$\mathscr L=\{\text{all the binary words such that the number of ones divide the number of zeros}\}$is non regular using the pumping lemma For example:$010010\in \...
Let it be L a regular language. Prove that exists a fast finite automaton (FFA) M which excepts L. Definition of FFA: FFA is a 6-tuple M=$<Q,Σ,P,δ,s,A>$ which: 1. Q is a finite set of ...
### Is $L = \left \{ a^m b^mca^nb^m \mid m,n \geq 0 \right \}$ context free language?
I have doubt , regarding this question Is this language is context free ? $L= \left \{ a^m b^mca^nb^m \mid m,n \geq 0 \right \}$ IMO : push all $a$'s , match with $a$ and pop $b$'s ,(now stack ...