Is the language ${L}_{n}$ regular?

  • Context: MHB 
  • Thread starter Thread starter JamesBwoii
  • Start date Start date
  • Tags Tags
    Language Regular
Click For Summary
SUMMARY

The language ${L}_{n}$, defined as ${L}_{n} = \{ a^{k} \mid k \text{ is a multiple of } n \}$ for each positive integer $n$, is regular. This conclusion is established by constructing a Non-deterministic Finite Automaton (NFA) or a Deterministic Finite Automaton (DFA) to represent the language. Additionally, a regular expression can be formulated for ${L}_{1}$ as $\{a\}^*$, which encompasses all strings of 'a' where the exponent is a non-negative integer. The discussion emphasizes the importance of understanding regular expressions to define regular languages.

PREREQUISITES
  • Understanding of regular languages and their properties
  • Familiarity with Non-deterministic Finite Automata (NFA) and Deterministic Finite Automata (DFA)
  • Knowledge of regular expressions and their syntax
  • Basic concepts of formal language theory
NEXT STEPS
  • Study how to construct NFAs and DFAs for specific languages
  • Learn to write regular expressions for various language patterns
  • Explore the Pumping Lemma and its implications for regular languages
  • Investigate examples of regular languages and their automata representations
USEFUL FOR

Students of computer science, particularly those studying formal languages, automata theory, and anyone interested in understanding the properties of regular languages.

JamesBwoii
Messages
71
Reaction score
0
Hi, I'm back with another question, but the opposite of last time.

The question is:

For each positive integer $n$, let ${L}_{n}$ = { ${a}^{k}$ $|$ $k$ is a multiple of $n$ }
Show that for each $n$ the language ${L}_{n}$ is regular. As far as I understand you cannot use pumping lemma to prove a language is regular.

I assume that leaves me with having to do a NFA, DFA or regular expression as I don't know where to begin to create one of those for this language.

Thanks!
 
Physics news on Phys.org
The easiest way to define regular languages is using regular expressions. Can you write a regular expression describing $L_1=\{a^k\mid k\ge0\}=\{a\}^*$?
 
Evgeny.Makarov said:
The easiest way to define regular languages is using regular expressions. Can you write a regular expression describing $L_1=\{a^k\mid k\ge0\}=\{a\}^*$?

Honestly no, I just can't see it. I'm really struggling with this particular problem sheet.
 
Then you should read the definition and examples of regular expressions, for example, in Wikipedia.
 

Similar threads

  • · Replies 18 ·
Replies
18
Views
3K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 24 ·
Replies
24
Views
4K
  • · Replies 1 ·
Replies
1
Views
2K
Replies
1
Views
2K
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K