As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [regular-language]

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.

1,232 questions
Filter by
Sorted by
Tagged with
19 views

25 views

### Is the following language is regular, context free, and/or decidable?

Given a language determine if it is regular, context free, and/or decidable. No proof needed, but an explanation would be appreciated. A = {a^n b^(2n+6) | n >= 0} My first guess is no its ...
65 views

63 views

### Algorithm to determine if $L_1$ is a subset of $L_2$ in Automata Theory

I need to create a pseudo Algorithm to determine if $L_1$ is a subset of $L_2$ where both are regular languages with a given DFA. I thought about creating the intersection automaton of $L_1$ and $L_2$ ... 58 views

### Proving irregularity using Myhill-Nerode theorem

I need to prove that L = { 0^(3n)1^(2n) | n>0 } is irregular using The Myhill-Nerode theorem I understand I need to demonstrate that it is not a finite union of ... 72 views

### Create regular expression not contain "aaa"

I have a question about creating regular expression out of the given language. The language is : 𝐿3 = {𝑤∈{𝑎,𝑏,𝑐}∗|𝑤 𝑑𝑜𝑒𝑠 𝑛𝑜𝑡 𝑐𝑜𝑛𝑡𝑎𝑖𝑛 𝑎𝑎𝑎} I'...
25 views

### Regular language: what is the Union of the iteration of 0's with the iteration of 1's

I'm taking the Edx Stanford compiler course and it shows $0*$ + $1*$ = $(0^i | i >= 0)$ u $(1^i | i >= 0)$ Sorry screen readers but in case my mathjax is illegible. In the second line it shows ...
56 views

### prove $a^nb^{n^2+n}$ is not regular by intersection

I want to prove that this language is not regular $L = a^nb^{n^2+n}; n \geq 0$ It proved a bit challenging to prove it directly, and thus I am looking for the intersection way. I want a regular $L_1$ ...
1 vote
82 views

### If $L_1L_2$ is regular language, is $L_2L_1$ regular as well?

If $L_1L_2$ is regular language, is $L_2L_1$ regular as well? I think the answer is no, but I'm not sure how to contradict.
49 views

### Numerical values for chance words. [closed]

We use probabilistic words such as "likely", "unlikely" and so in normal conversation. I would like for these rather vague notions to be given some mathematical precision. As a ...
66 views

### Prove $NOTCONTEXTFREE_{TM}$ is not recursively enumerable?

$NOTCONTEXTFREE_{TM}$ = {$\langle M \rangle$, M is a turing machine and the language of M is not context-free}. I'm trying to prove the language $NOTCONTEXTFREE_{TM}$ is not recursively enumerable. I'...
1 vote
59 views

### Determine if language $L=\{xyxz\,\,|\,\,x\neq\varepsilon,\,\,x,y,z\in\{0,1\}^{*}\}$ is regular

Question. Determine if the language is regular: $L=\{xyxz\,\,|\,\,x\neq\varepsilon,\,\,x,y,z\in\{0,1\}^{*}\}$ I think $L$ is non regular, because of the second x. I'm trying to prove with the ...
40 views

### Determine if language is regular

Question. Determine if the languages are regular: $L_{1}=\{(ab)^{k}a(ba)^{k}\,|\,k\geq0\}$ $L_{2}=\{(ab)^{k}b(ba)^{k}\,|\,k\geq0\}$ I think both are not regular, I used the Pumping Lemma to prove, ...
61 views

### Prove that the language is not regular without using the Pumping Lemma

Question. Prove that the language is not regular without using the Pumping Lemma: $L=\{a^{n}b^{m}c^{k}\,\,|\,\,n^{2}+m^{2}=k^{2}\}$ Attempt. I assume that L is regular, and I am trying to use ...
### Find regular expression for a given language $L=\{0^{n}1^{m}\,\,\,|\,\,\,n+m(mod3)\neq0\}$
Question. Write a regular expression for the language: $L=\{0^{n}1^{m}\,\,\,|\,\,\,n+m(mod3)\neq0\}$ Attempt. $r=(000)^* (0(ε+0+1+011)+1(ε+1)) (111)^*$ Is my regular expression correct? If so, is ...