111 questions linked to/from How to prove a language is regular?
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: ...
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 ...
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, ...
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 ...
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?
1k views

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?
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?
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?
### 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.