Two computational theory language questions - multi choice

I feel that this is some old homework assignment you found someplace. I think it needs to be tossed, as it is unclear what is being asked.What is a "generator" for a language? Is it like a minimal set of strings that generate all strings in the language? If so, then none of the four choices generate the language for question 2.##4)## can generate the string ##ba##.In summary, the conversation discusses two questions. The first question involves finding an example of a set S where S* has the same number of 8-letter words as 4-letter words. The second question asks for a suitable generator for the language NOTABandEVEN, which consists of all even length words that
  • #1
Lord Anoobis
131
22

Homework Statement


##1)## Which one of the following is an example of a set ##S## such that the language ##S^*## has the same number of 8-letter words as 4-letter words?
1) ##S = \{aaaa \quad bbbb\}##
2) ##S = \{bbbb \quad bbbbbb\}##
3) ##S = \{aa \quad bb\}##
4) ##S = \{a \quad bbbb\}##

##2)## Consider the language NOTABandEVEN over ##\{a \quad b\}## consisting of all words of even length that do not contain the substring ##ab##. Which one of the following is a suitable generator?
1) ##baa##
2) ##bbbaab##
3) ##ba##
4) ##babb##

Homework Equations


None.

The Attempt at a Solution


In the first question we can easily eliminate 3 and 4. 1 has two possibilities for both four-letter and eight-letter words. 2 has one possibility for each, so we have two correct answers. Or have I overlooked something?

In the second question all of the given strings result in words containing the forbidden substring. The only possibility I see is option 3 with the only word generated being ##ba##, so the language in question consists of only one word. Correct?
 
Physics news on Phys.org
  • #3
For question 1, choice 1, I get 4 8-letter words, and only 2 4-letter words.

It's not clear what is meant by generator in question 2. Generally a language is generated by a grammar, or a set of production rules. The meaning here seems to be like a generator for a group: ab, generates {∅, ab, abab, abababab, ...}. The problems is that any string with one or more a 's and one or more b's in it will fail, and you won't generate the entire language anyway. something like this is needed:
S→BA
A→aA
B→bB
A→∅
B→∅
∅ is the empty string
 
  • #4
jedishrfu said:
Wouldn't bbaa and bbbaaa ... be members too for question #2?

For question #1, choice 2 says bbbb or bbbbbb so doesn't the bbbbbb exclude it as well since bbbbbb is 6 characters in length?
The question seems to limit one to words resulting from concatenating the given strings so I assume ##bbaa## and ##bbbaaa## do not qualify. Quite frankly I feel both questions are a bit vague.
 
  • #5
willem2 said:
For question 1, choice 1, I get 4 8-letter words, and only 2 4-letter words.
Okay, I can see that now. I neglected the possibilities of all ##a## and all ##b##. As for the term "generator" in question 2, I agree that it is far from clear and one has to assume what it requires.
 
  • #6
Thanks for the input.
 

Related to Two computational theory language questions - multi choice

1. What is computational theory?

Computational theory is a branch of computer science that deals with the study of algorithms, computation, and information processing. It aims to understand how computers solve problems and how they can be used to solve real-world problems.

2. What is the importance of computational theory?

Computational theory is important because it provides a framework for understanding how computers work and how they can be used to solve complex problems. It also helps in the development of new algorithms and software that can be used in various fields such as artificial intelligence, data analysis, and cryptography.

3. What are the different types of computational theory?

There are several types of computational theory, including automata theory, complexity theory, computability theory, and algorithmic information theory. Each type focuses on a different aspect of computation and has its own set of tools and techniques for analyzing and solving problems.

4. What is the difference between computational theory and computer science?

Computational theory is a subfield of computer science, which is a broader discipline that encompasses the study of computers and computational systems, their design and development, and their applications. Computational theory focuses on the theoretical foundations of computation, while computer science also includes practical aspects such as programming and software engineering.

5. How is computational theory used in real-world applications?

Computational theory is used in various real-world applications, such as artificial intelligence, machine learning, data analysis, and cryptography. It provides the fundamental concepts and tools for developing efficient algorithms and solving complex problems that are essential in these fields. For example, computational theory is used in developing algorithms for speech recognition, image processing, and natural language processing in AI systems.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
981
  • Set Theory, Logic, Probability, Statistics
2
Replies
40
Views
6K
  • Computing and Technology
2
Replies
44
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Art, Music, History, and Linguistics
Replies
9
Views
2K
  • Programming and Computer Science
Replies
1
Views
1K
  • Quantum Interpretations and Foundations
Replies
13
Views
2K
  • Special and General Relativity
Replies
11
Views
351
  • General Math
Replies
1
Views
767
Back
Top