[Math] How to check if a language is regular

automatacontext-free-grammarformal-languagesregular-language

I'm currently studying a formal languages & automate module on my course and I have been asked to answer the following question:

Which of the languages below are regular? If the language is regular, justify your answer by giving the corresponding regular grammar, or by referring to lemmas

$$\{a^n b^m \mid n, m \ge 1\}$$

I've worked with grammars and derivations of productions of grammars but I'm unsure how to prove if a language is regular or not.
After researching online I believe I need to use pumping lemma but I'm unsure how to actually use the lemma to solve a question like this and would appreciate if somebody could do a step by step on how to solve a question like the one above or point me in the direction of some useful material.

I believe the above language is context-free not regular.

Thanks in advance,

Best Answer

If you want to use lemmas, note that $$ L:= \{a^nb^m : n,m \ge 1\} = \{a^n : n \ge 1\} \circ \{b^m : m \ge 1\} $$ that both languages on the right are regular, and regular languages are closed under concatenation.

To give a grammar, show that $$ S \to aA, A \to aA | B, B \to bB | b $$ with starting symbol $S$ generates $L$.

Related Question