# Questions tagged [regular-languages]

Questions about properties of the class of regular languages and individual languages.

211 questions
Filter by
Sorted by
Tagged with
1k views

### Given 2 regular languages and their DFA's, how to construct the DFA of the union?

Suppose $L1, L2$ are both regular languages and $A1, A2$ are their corresponding DFA's. How can I construct a new DFA for the regular language $L1 \cup L2$?
78 views

### Regular languages and sets proof

I just have general questions about sets and determining if they are regular languages. i) If A is regular, and A is a subset of B, then B must be regular. ii) If B is regular, and A is a subset of ...
48 views

4k views

### DFA that accepts decimal representations of a natural number divisible by 43

First, I have tried to build a DFA over the alphabet $\sum = \{0,\dots, 9\}$ that accepts all decimal representations of natural numbers divisible by 3, which is quite easy because of the digit sum. ...
4k views

### Show that every infinite language has a non-regular subset

I'm trying to solve this problem: Let $L$ be some infinite language, show that there exists a sub-language of $L$ that is not regular But can this be correct? If I have the language $\{a\}^*$ for ...
2k views

### Understanding application of Arden's theorem to find regular expression

I learnt Ardens theorem and its usage as follows: Ardens Theorem Let $P$ and $Q$ be two regular expressions over alphabet $Σ$. If $P$ does not contain null string, then $R = Q + RP$ has a ...
347 views

### Proof: There exists an irregular language L such that LLLL is regular

As title. I consider finding a specific L to fulfill the condition stated to prove the statement, however, I have no luck in finding one. A senior gave me a hint that Lagrange's four square theorem ...
605 views

### If set membership problem can be solved for a particular language does this imply that the language is regular?

If we know that a language is regular, we can solve the set membership question for a given string by running it through the corresponding DFA for that language. But what about the other way? Means, ...
3k views

### How can I prove that the language of a read-only Turing machines is regular?

I find this, but I can't complete it, is there any other solution for it?
432 views

### How I can find all equivalence classes by Myhill-Nerode?

first of all I'm sorry for my bad English and second I'm sorry for my mistakes of understanding the following topic, I still going to school and learning this for interest. The topic is Myhill-Nerode ...
### Myhill-Nerode equivalence classes of $\{1^n0^n\}$
I have the following task and its solution. Question Given the language $$A \triangleq\left\{1^{n} 0^{n} \mid n \in \mathbb{N}\right\} \text { with } \Sigma_{A} \triangleq\{1,0\},$$ ...