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.
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 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
What did Darwin think about how languages changed over time? Group of answer choices A. They...
What did Darwin think about how languages changed over time? Group of answer choices A. They evolved via natural selection B. That different languages affected an individuals ability to survive and reproduce C. They were influenced by genes D. That it was a completely different process to biological change.
C++ How do I use ASC II in order to see if an alphabet is lowercase...
C++ How do I use ASC II in order to see if an alphabet is lowercase or uppercase? Please show me how to do this.
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT