Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,881 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
1
vote
0
answers
62
views
Prove that $ L = \lbrace a^m b^n \mid m \neq n^2 \rbrace $ isn't CFL
I've got following statement (as a challenge, not as a hw or something), being told that it's kinda hard to prove it
$ L = \lbrace a^m b^n \mid m \neq n^2 \rbrace $ isn't CFL
Following statement (I ...
5
votes
1
answer
632
views
Are definite languages closed under Kleene Star?
This question came up while solving a problem in a Language Automata textbook, in which a definite language is defined as:
"a language L is definite if there is a number k where for every string ...
1
vote
2
answers
46
views
Regularity of Languages $L_1$ and $L_2$
I am analyzing the regularity of the following two languages defined over the alphabet $\Sigma = \{a, b\}$:$$L_1 = \{ \alpha \beta \alpha \mid \alpha \in \{a, b\}^+ \text{ AND } \beta \in \{a, b\}^+ \}...
0
votes
1
answer
65
views
If Σ* union with CFL/CSL etc still gives Σ*, is language always regular?
I have language of form wxwt where w ∈ {a,b}* and x ∈ {a,b}* . If I take w = ε then it becomes x, and since x ∈ {a,b}* this gives Σ*. Other cases like wwt (CFL) or wwwt (CSL) also appear, but union ...
2
votes
0
answers
56
views
Translating star-free $\omega$ -regular expressions to LTL formulae
It's known that LTL formulae describe star-free languages, but is there a good method to translate star-free $\omega$-regular expressions (i.e. expressions of the form $X\cdot Y^\omega$ where $X$ and $...
2
votes
2
answers
178
views
Proving α2 ≤ α1 + |w| + 1 for Myhill-Nerode equivalence classes when adding a word w to a regular language
Let $\Sigma$ be a finite alphabet and let $L_1 \subseteq \Sigma^{\ast}$ be a
regular language. Pick a word $w \in \Sigma^{\ast}$ and define
$$
L_2 := L_1 \cup \{w\}.
$$
For $i \in \{1,2\}$ let $\...
5
votes
2
answers
667
views
Proving the non-regularity of a language
Consider the Language $L=\{aba:a\in0^{+}, b\in \{0,1\}^{+}\}$ over the alphabet $\{0,1\}$
Claim:- $L$ is a non-regular language
Proof:- Suppose $L$ is regular. Then by pumping lemma there exists a ...
0
votes
1
answer
77
views
How do you construct an even linear grammar from a finite automaton?
Even linear languages are defined in On a family of linear languages.
These languages are generated by special linear grammars, called even linear grammars (ELG), having only rules of the form
$A \to ...
4
votes
1
answer
238
views
Does every infinite recursive language contain a non-recursive RE subset?
Let $L \in R$ be an infinite recursive language. Is it always possible to find a subset $L' \subseteq L$ such that $L' \in \mathbb{RE} \setminus R$?
In other words, can every infinite decidable ...
3
votes
1
answer
92
views
Does the language $L = \{,0円^i1^j \mid \exists k\in\mathbb{N},,円j = k,円i\}$ satisfy pumping lemma?
I tried to apply the pumping lemma to the following language:
$$L = \{,0円^i1^j \mid \exists k\in\mathbb{N},,円j = k,円i\}$$
First I select a constant N and a word:
$$
w = 0^i1^{k,円i}\quad\text{with }i\...
3
votes
2
answers
1k
views
Does concatenating a language with Σ* always result in the universal language?
I'm trying to understand how language concatenation works with the universal language (i.e., Σ*). Suppose I have a language like L = {an}, and I concatenate it with the universal language. For example:...
-4
votes
1
answer
100
views
Is the language {xwwy | w,x,y ∈ Σ∗ : w,x,y != ε}, where Σ = {0,1}, regular?
Question as in the title. If it is non-regular how to do both Pumping Lemma and Myhill-Nerode Proof.
3
votes
2
answers
110
views
What exactly $y$ is in Pumping Lemma when string is partitioned into $w=uyw$?
Pumping Lemma : For any regular language $\mathbb{L},ドル there exists an integer $P,ドル such that for all $x\in \mathbb{L}$ with $|x|\geq P,ドル there exists $u, y, w \in \Sigma^*,ドル such that $x = uyw,ドル and
...
4
votes
2
answers
166
views
Determinize History-Deterministic Automaton By Pruning
A known result is that History-Deterministic automaton for finite words contains a deterministic automaton that accepts the same language.
Meaning, we can achieve a deterministic automaton for the ...
2
votes
1
answer
94
views
Why are the inference rules of Salomaas axiomatization of regular events problematic?
In Salomaa's Jewels of formal language theory, Ch. 2 Exercise 8 asks you to prove the completeness of a system which, after digging around for a bit, turns out to be a result of one of his papers (...