# Tagged Questions

Regular languages are formal languages which are recognized by a finite automaton. It is equivalently the languages which are expressible as a regular expression. In addition to these two, there are several other equivalent definitions.

41 views

### Why does a certain turing machine only accept regular languages?

why does a single tape turing machine, which can not write on the part of its tape containing the input, only accept regular languages? I am asking this because this question is being opposed to me ...
45 views

### Product of two DFA.

Let $A, B \subset \{ a, b\}^*$ and $A, B$ be regular. Lets define: $A \circ B = \{ w \in A | \exists y \in B , \#_aw = \#_ay \}$ where,for example: for $w = aaabaaba$ $\#_aw = 6, \#_bw = 2$ ...
13 views

19 views

### If $L$ is context-free, then $L$ is regular

Let $L \subset \{a\}^*$ and assume that $L$ is context-free. Prove that $L$ is regular. Please hint me.
20 views

32 views

### How many states (minimally) for an automaton recognizing the set of words without palindromic subwords on a $k$-letter alphabet?

Let $\Sigma_k = \{0,1,...,k\}$ and let $NPA_{k}$ be the set of words that do not contain a palindrom (of length $\ge 2$) as a subword. How many states (minimally) must have an automaton that ...
26 views

### Check if $L$ is regular then $L'$ is regular (and and vice versa)

let's define $w\leftrightarrow v$. It does mean that we may "create" $w$ using word $v$ in following way: every single letter $x\in \Sigma$ in word $v$ may be replaced by $xx$, and every double ...
41 views

### Are all finite languages regular?

I've been thinking about this for a while and still cannot come up with a way to show that all finite languages are regular. I know that all finite languages consist of finite number of strings that ...
49 views

### Prove the following language is not regular using pumping lemma.

Prove the following language is not regular using the pummping lemma $L = \{a^{n!} \mid n\geq0, n\in\ \mathbb{N} \}$. What I have done so far is: Assume $L$ is regular. So, there is a $DFA$ for $L$ ...
2k views

### Why are every finite language decidable?

I don't understand why every finite language is decidable. For example, if I have an infinite set of strings L over an alphabet E, why is there a Turing Machine M that decides L? I understand the ...
30 views

44 views

44 views

30 views

### Understanding pumping lemma - length $p$ - in connection with other thread

I create this thread in connection with Is the following language $L$ regular? I would like to show you why I dont understand where I am wrong. I would like to ask question: $p$ - length of pumping ...
77 views

### Trouble with induction on the length of a word

In the accepted solution of the question If L is regular, prove that $\sqrt{L}=\{w:ww\in L\}$ is regular the answerer made the claim that "What's left is to show that $δ ′ (q_{0}' ,w)=h$ , which can ...
159 views

### $L$ is regular. Show that $Root(L)$ is also regular
Let $Root(L)=\{w \mid \exists {n\in \mathbb{N}} \text{ such that } w^n\in L\}$. How to deal with it ? I tried think about modifications connected with automat for $L$, but it failed. Help me, please.
### show that language $L'$ is regular (given $L$ regular)
Let $L$ be a regular language. Show that $L'=\{x \mid\exists_{y,z} xyz\in L \text{ and }|x|=|y|=|z|\}$ is also regular. Firstly I show my idea. When you accept it I will try to formalize it. Every ...