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

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

Discussion Overview

The discussion revolves around the regularity of the language ${L}_{n} = \{ a^{k} \mid k \text{ is a multiple of } n \}$ for each positive integer $n$. Participants explore methods to demonstrate that this language is regular, focusing on the use of regular expressions, NFAs, or DFAs.

Discussion Character

  • Homework-related
  • Technical explanation

Main Points Raised

  • One participant asks how to show that the language ${L}_{n}$ is regular, expressing uncertainty about using the pumping lemma.
  • Another participant suggests that a regular expression could be used to define $L_1$ and asks for a specific regular expression for $L_1$.
  • A third participant admits difficulty in writing a regular expression for $L_1$ and expresses struggle with the problem sheet.
  • A later reply recommends reviewing the definition and examples of regular expressions, specifically referencing Wikipedia as a resource.

Areas of Agreement / Disagreement

Participants do not reach a consensus on how to approach the problem, and there is a clear expression of uncertainty regarding the formulation of regular expressions.

Contextual Notes

Participants have not provided specific definitions or examples of regular expressions, and there is an indication of missing foundational understanding that may affect the discussion.

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