Question

How do we know that the number of languages over a finite alphabet are uncountable?

How do we know that the number of languages over a finite alphabet are uncountable?

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

The solution for the problem is provided below, please comment if any doubts:

  • Let ∑ be a finite alphabet, then there are ∑* strings are possible with it which is an infinite set.
  • A language over an alphabet is a subset of strings over ∑, that is subset of ∑*.
  • According to set theory, number of subsets possible using a set of size n is 2n.
  • Here n is infinity.
  • So number of languages = 2∞ = infinity.

That is the number of languages over finite alphabet is infinity or uncountable.

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Let F be the set of all finite languages over alphabet {0, 1}. Show that F...
Let F be the set of all finite languages over alphabet {0, 1}. Show that F is countable
Q2 [10 pts] Give DFA's accepting the following languages over the alphabet {0,1}: a) The set...
Q2 [10 pts] Give DFA's accepting the following languages over the alphabet {0,1}: a) The set of all strings whose 3rd symbol from the right end is a 0. b) The set of strings such that the number of 0's is divisible by 3 and the number of 1's divisible by 2.
1. Define a deterministic finite automaton over the alphabet {a, b} which accepts the set of...
1. Define a deterministic finite automaton over the alphabet {a, b} which accepts the set of all strings that end with the substring ab or ba.
Which one of the following languages over the alphabet {0,1} is described by the regular expression...
Which one of the following languages over the alphabet {0,1} is described by the regular expression (0+1)* 0 (0+1)* 0 (0+1)* ? a.The set of all strings that begin and end with either 0 or 1 b.The set of all strings containing at most two zeros c.The set of all strings containing at least two zeros. d.The set of all strings containing the substring 00
n digit string of length n over alphabet {0,1, . . . ,9} a. How many...
n digit string of length n over alphabet {0,1, . . . ,9} a. How many n digit strings are there with at least one 1? b. many n digit are there with EXACTLY one 1? PLEASE ANSWER BOTH AND INCLUDE THE FACT THAT THE STRING IS OVER ALPHABET {0,1,2,3,4....9}
should we all know how to do the Heimlich maneuver?
should we all know how to do the Heimlich maneuver?
How many strings over alphabet Ʃ = {a,b} are there a) of length 5? b) of...
How many strings over alphabet Ʃ = {a,b} are there a) of length 5? b) of length at most 5? c) of length ?? d) of length at most ??
how we can know the number of trays if we have 3 three equilibrium stages and...
how we can know the number of trays if we have 3 three equilibrium stages and trays efficiency equal to 0.8
How do we know how many genes control development in an organism like Drosophila? And how...
How do we know how many genes control development in an organism like Drosophila? And how did we discover that selector genes specify which adult structures will be formed by body segments? Additionally, how do we know that eye formation in all animals is controlled by a binary switch gene?
why is there constant temperature and pressure at equilibrium? how do we know this
why is there constant temperature and pressure at equilibrium? how do we know this
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT