# Tagged Questions

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

219 views

### Prove that $wu=uw$, given that $w^5=u^3$

Suppose $w,u\in\Sigma^*$, $w^5=u^3$, and I need to show that $wu=uw$. I started with $5|w|=3|u|$, but I didn't know how to continue... any suggestions?
46 views

### Which of these languages are regular?

Consider the following subsets of $\{ a, b, \$ \} ^*$:$A = \{ xy \mid x,y \in \{ a, b, \} ^*, \#a(x) = \#b(y) \}$and$B = \{ x \$y \mid x,y \in \{ a, b, \} ^*, \#a(x) = \#b(y) \}$. Which of the ...
53 views

### How can I implement a Deterministic finite automaton which accepts strings having specific words.

I am trying to make a Deterministic finite automaton which accepts those strings having two specific words(either one) anywhere as a substring. The problem is really simple if the characters of the ...
37 views

### Writing a Context Free Grammar for a language with multiple strings in the language

I have an interest in computing and want to learn more about the actual theory behind it. Context Free Grammar plays a part and I am quite fascinated by it all. However, I came with a language that ...
43 views

### What is the language of following CFG?

A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals. $$S → aS \mid A \\ A → aAb \mid bAa \mid \epsilon$$ Which of the following ...
36 views

### How we derive language from grammar by bottom up or any other approach?

Consider a CFG with the following productions. S → AA | B A → 0A | A0 | 1 B → 0B00 | 1 $S$ is the start symbol, $A$ and $B$ are non-terminals and $0$ and $1$ are ...
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: ...
46 views

### proving that a regular language can be accepted by a fast finite automaton

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 ...
60 views

### proving that $L_\text{almost}$ is a regular language

Let it be L, a regular language. we will define: $L_\text{almost} = \{ w'\mid \exists w\in L\ w' \text{ is almost similar to }w \}$ a word $w'$ is almost similar to $w$ if they are in the same length,...
16 views

### If $L_1$ and $L_2$ are non regular then $L_1 \cup\;L_2\; = L$ can be regular?

I need to prove or disprove with contrast example: If $L_1$ and $L_2$ are non regular then $L_1 \cup\;L_2\; = L$ can be regular I have no idea how to begin, hints and spoilers are welcomed
46 views

105 views

### Create a formal regular expressions that accepts all strings of 1 and 0 that do not contain 101

I'm working through a textbook on automata theory and I'm stuck on this regular expression problem. Create a regular expression for the following language: The set of all strings that do not contain ...