# How many words of length n are there in this regular language?

• SashaRulez
In summary, the problem is asking to show that a regular language L has infinitely many binary words of length n that are a subset of the language S, which is a subset of L. The attempt at a solution involves using the regularity of L and its finite automaton to relate the number of words to states/transitions. However, the solution may not be possible as L and S could both be empty languages.
SashaRulez

## Homework Statement

I am self studying automata theory and I found a problem set from an old class I took a few years ago, but I have no clue how to solve the following problem, any help would be appreciated.Suppose we have a regular language ##L \subseteq \{0,1\}^*## and the language ## \mathbf{S} = \{uu: u\in \{0,1\}^*\}## is a subset of ##L##. Clearly for even ##n## there are at least ##2^{n/2}## words of length ##n## in ##L##. How would I show that there are at least ##a2^n## length ##n## binary words in ##L##, for infinitely many ##n##, without using the Myhill-Nerode theorem? Where ##a## is some constant that can depend on ##L##.

## The Attempt at a Solution

Clearly ##\mathbf{S}## is non-regular, so there must be more length ##n## words accepted, but I am not sure how to get ##\Theta(2^n)## length ##n## words. Somehow one has to use the regularity of ##L##, so maybe take its finite automaton, and relate the number of words to states/transitions? I don't see a way to proceed.

Last edited:
SashaRulez said:

## Homework Statement

I am self studying automata theory and I found a problem set from an old class I took a few years ago, but I have no clue how to solve the following problem, any help would be appreciated.Suppose we have a regular language ##L \subseteq \{0,1\}^*## and the language ## \mathbf{S} = \{uu: u\in \{0,1\}^*\}## is a subset of ##L##. Clearly for even ##n## there are at least ##2^{n/2}## words of length ##n## in ##L##.
Wait. L is a subset of ##\{0,1\}^*##, not necessarily equal to the whole thing. For all we know, L could be the empty language. Similarly, S could be the empty language. There need be no more than zero words of length n for any given n.

Regardless of n, 0 < 2^n and it would seem that the obvious claim is falsified.

There is an obvious choice of "a" that makes for an easy solution to the problem as stated.

## 1. How do you define a regular language?

A regular language is a set of strings that can be generated by a finite automaton or expressed using regular expressions. It follows a set of rules and patterns, making it predictable and easy to understand.

## 2. What is the length of a word in a regular language?

The length of a word in a regular language is the number of symbols or characters it contains. This can vary depending on the specific language and its rules.

## 3. How do you determine the number of words of length n in a regular language?

The number of words of length n in a regular language can be determined by analyzing the rules and patterns of the language. It may also involve using mathematical formulas and techniques such as combinatorics.

## 4. Can the number of words of length n in a regular language be infinite?

Yes, the number of words of length n in a regular language can be infinite if the language allows for an infinite number of combinations and patterns. However, some regular languages may have a finite number of words of a certain length.

## 5. How does the length of a word affect its complexity in a regular language?

The length of a word can affect its complexity in a regular language, as longer words may require more rules and patterns to generate. However, this can vary depending on the specific language and its structure.

• Engineering and Comp Sci Homework Help
Replies
8
Views
1K
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
1
Views
3K
• Calculus
Replies
1
Views
345
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K