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

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.
  • #1
SashaRulez
1
0

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:
Physics news on Phys.org
  • #2
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.
 

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

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.

Similar threads

  • 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
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
Back
Top