6
It's important to distinguish between regular grammars and regular languages.
Your first grammar is regular.
A regular grammar is either a right-regular grammar or a left-regular grammar. In a right-regular grammar, every production's right-hand side has at most one non-terminal, and that non-terminal is the last symbol in the right-hand side. A left-...
3
$\Sigma$ does not include the empty string; it only contains the characters of the language, and the empty string is not a character. As user ttnick said in a comment, in general, if $\Sigma=\{x_1,x_2,\dots,x_n\}$, then "$\Sigma$" in a regex represents $x_1 + x_2 + \dots +x_n$ (equivalently $x_1 \cup x_2 \cup \dots \cup x_n$, depending on what notation you'...
2
Let us prove a more general result:
For each $m \geq 2$ there is a language $L$ such that $L,L^2,\ldots,L^{m-1}$ are not regular but $L^m$ is regular.
The language we construct will be unary, that is, of the form $L = \{a^n : n \in S\}$, where $S \subseteq \mathbb{N}$ is
$$
S = \{ km : k \geq 0 \} \cup \{ m^k + 1 : k \geq 1 \}.
$$
Let $1 \leq p \leq m-1$,...
2
Consider, for instance, $A = \{ \varepsilon \}$. Then $X = AX$, so $X = AX \cup B$ holds for any $X$ with $B \subseteq X$.
1
You are correct that the grammar $S \rightarrow aS \mid \lambda$ is regular. However, there are a lot of regular languages out there (a countably infinite number in fact!), so even if your grammar doesn't look like this, it can still be a regular language.
The standard way to show that a language is regular is to write a regular expression for it (or build ...
1
Unless you must deal with unary regular languages, there is no need for complex math ...
Just pick an irregular language that is able to "capture and mask" the concatenation of itself; e.g. over $\Sigma = \{a,b \}$
$L = \{ (a^ib^j) (a^n b^n) \mid i, j \geq 1, n \geq 1\} \; \cup \; $
$ \{ (a^ib^j)^k \mid i, j \geq 1, k \neq 2\}$
$LLLL$ is equal to ....
1
In typical usage of the pumping lemma, you assume that the word you chose for pumping is written as $w=xyz$, with $x,y,z$ satisfying the conditions of the pumping lemma.
Then, in most cases, you reach a contradiction by saying that e.g., $xy^2z$ is not in the language. This is "pumping up", since you "add" copies of $y$.
In this case, however, you reach a ...
1
Your question doesn't make sense because of a category error. "Regular" is a property of sets of strings. A set of languages is a set of sets of strings, so it doesn't make sense to ask if it's regular.
Only top voted, non community-wiki answers of a minimum length are eligible
