# Linked Questions

111 questions linked to/from How to prove a language is regular?
3answers
5k views

### Build a regular grammar for a regular language [duplicate]

The language considered is the infinite set of all chains that meet the following conditions. Conditions: ...
1answer
19k views

### DFA - Accept all strings that does not contain a certain substring [duplicate]

So I have been trying to create a Deterministic Finite Automaton(DFA) in Jflap that accepts all strings from the alphabet {a, b, c} except those that contain the substring "abc". However i ...
1answer
4k views

### Decide whether the Language is regular {a^i b^j c^k|i ≥ 0, j ≥ 0, k ≥ 0} [duplicate]

how would you prove if this language is regular/irregular? question given: Decide for each of the following languages whether it is regular. If so, design a DFA/NFA for recognizing it, and if not, ...
1answer
1k views

### How do I prove that a language is regular? [duplicate]

In order to prove that the following language is regular, would I use a pumping lemma? The set $A$ of all strings that are substrings of some string in $L$, where $L \subseteq\Sigma^*$. $L$ Must be ...
1answer
1k views

### What is the regular expression for strings containing at least one a and at least one b? [duplicate]

$L = \{w \in \{a, b, c\}^*\mid w\text{ contains at least one }a\text{ and at least one }b\}$. what's the proper regular expression for the following language?
1answer
1k views

1answer
291 views

### How can I build a DFA for ${a^m b a^n | m+n \equiv 1 mod 3}$? [duplicate]

I have a language $\{a^m b a^n | m+n \equiv 1 mod 3\}$ $m+n$ can be 1, 4, 7, 10, 13, 16, 19, 22, ... $m+n$ is the number of all $a$'s in the word How can I build a DFA for this language?
1answer
135 views

### Prove A² is regular [duplicate]

Suppose that $A$ is a regular language. How can I show that $A^2 = A \cdot A$ is a regular language? Is there a construction?
1answer
214 views

### To prove or disprove that language is regular [duplicate]

Suppose the language L = {w | w is an integer whose sum of digits is a multiple of 2}. I strongly feel like this is non-regular language, but how should I choose a string to apply the pumping lemma?
1answer
177 views

### Provide “regular” grammar for this language {${a^ib^j \mid i>0\ and \hspace{2.5mm}i\leq j \leq(2*i)}$} [duplicate]

I'm trying to understand the approach to constructing an grammar which accepts the language ${a^ib^j \mid i>0\ and \hspace{2.5mm}i\leq j \leq(2*i)}$ } Thanks.
1answer
194 views

let's have these two languages in the alphabet $\{a,b,c\}$: $L_1 = \{ w \mid w \text{ is a palindrome and$|w| < 200$}\}$ $L_2 = \{ w \mid w \text{ is a suffix of$u$and$|u|$is a prime number ... 2answers 174 views ### Proving that a derived language is regular [duplicate] Suppose I have a DFA recognizing a regular language$L\$, how do I prove that $$\text{lefthalf}(L)= \{ w_1 \mid \exists w_2 \in \Sigma^* ,w_1w_2 \in L \land \|w_1\| = \|w_2\| \}$$ is also a regular ...

15 30 50 per page