# Tagged Questions

Questions related to formal languages, grammars, and automata theory

43 views

32 views

### Why L = L^2 for the non-regular language L = {a^nba^n | n=>0}*?

I can't seem to understand why does L=L^2 for: L = {a^nba^n | n=>0}* Thanks!
16 views

### Prove that half(L) is also regular if L is a regular language [duplicate]

Given a regular language $L \subseteq \sum^*$ prove that the language $half(L) = \{w \space | \space ww \space \in \space L \}$ is also a regular language. -- Please give a hint or two. Have ...
40 views

311 views

### Does there exist context-free grammar with words of length n^2 or n^3?

Does there exist context-free grammar with words of length $n^2$ or $n^3$? I can't see any, we can produce all grammar with words of length $n$ ($S \to Se$), but then it seems to be impossible to ...
49 views

### L ={a^n.b^n | n>=0} , what is difference between L^2 and L.L?

which option is correct? please explain why other are wrong if any one is correct
72 views

### CFG Equivalent of regular expressions

So I was wondering something about the Chomsky hierarchy. DFAs (and NFAs) accept regular languages, while NPDAs accept context-free languages. Right-regular or left-regular grammars produce regular ...
83 views

### Is intersection of regular language and context free language is “always” context free language

I have read that intersection of regular language and context-free language is always context-free. Most of the places an standard example has been used to prove this, e.g., \begin{align*} L_1 &= ...
80 views

### Concatenation of $a^p$ and $a^m$ where $p$ and $m$ are primes, is irregular?

I believe that the concatenation $a^pa^m$ where $p$ and $m$ are primes is not regular, since I can show that $a^p$ is not regular using the pumping lemma, therefore there is no NFA for the 1st part, ...
79 views

### How to prove that a language $A$ is decidable?

How to prove: A language $A$ is decidable $\Leftrightarrow$ if there is a turing machine which lists $A$ in a word length alphabetically ordering. Word length alphabetically means a sorting first ...
46 views

### Is the punctuation part of the alphabet?

Given a language $L \subseteq \Sigma^*$, (it could be Italian, English, C++ or anything else), should we consider the punctuation (".", ";", "->") as a part of the alphabet $\Sigma$ upon the ...
60 views

### How to Trace Path in Proof that Regular Languages are Closed Under Reversal

I'm self studying automata theory and I need help with proving that regular languages are closed under reversal. I have a basic proof, but am unsure about last statement in my proof. Is this ...
13 views

11 views

### Struggling with Pumping Lemma application [duplicate]

I have studied Pumping Lemma carefully and have solved many exercises about it but I can't get an idea on how to solve this one: can anyone help me? Let L = { w#x | x is a substring of w }. Prove ...
52 views

### Why DCFL is not closed under kleene star?

I have read somewhere that DCFL is not closed under kleene star. but I haven't found any example
671 views

### Why are regular expressions defined with union, concatenation and star operations?

A regular expresssion is defined recursively as $a$ for some $a \in \Sigma$ is a regular expression, $\varepsilon$ is a regular expression, $\emptyset$ is a regular expression, $(R_1 \cup R_2)$ ...
46 views

### Of which Chomsky-type is the language $L = \{a^jb^ic^{2i} | i,j \in \mathbb{N}^0\}$?

At first I thought the language would be context sensitive because it seems that it can be shown with the pumping lemma for regular languages, that it's not a regular language and analogously with the ...