102 questions linked to/from How to prove a language is regular?
3k 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: ...
13k 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 keep ...
2k 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, ...
415 views

How to prove this language is regular [duplicate]

Let $L$ be a regular language with alphabet $\Sigma = \{a,b,c\}$. Prove that the following language is regular: $\{w | w \in L \text{ and } w \text{ starts with } abc \}$. I wonder what proof ...
515 views

Prove a language is regular - Regular language of 0's and 1's [duplicate]

I'm new to regular languages and I've been struggling to solve one for a while. The question is: If there exists a regular language L1 which has an alphabet {0,1}, prove that L2 is also a regular ...
274 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 ...
125 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?
391 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?
389 views

Prove a language is regular [duplicate]

I am asked to find Prove that the following languages are regular languages: (a) $\{a^nb^ma^k \mid n\geq3,m\geq1,k\geq1\}$ (b) $\{a^n \mid n\neq3 \text{ and } n\not\equiv2 \mod7\}$ ...
232 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?
295 views

I don't want to create a duplicate question of How to prove a language is regular?, I only want to know what is a good and simple way to explain why a language like $\qquad \displaystyle L = \{w \in \... 2answers 164 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 ... 1answer 178 views Prove language is regular [duplicate] 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 ...
$\{ w∈(a,b)^\ast | w$ does not contain '$ab$' as a subword $\}$. About questions like this, I always want to construct the regular expression for it, then convert the regular expression to a finite ...