Computer Science theory doubts

• colt
In summary, theoretical computer science focuses on fundamental principles and concepts, while practical computer science applies these theories to real-world problems. Key areas in computer science theory include algorithms, automata theory, and data structures. It contributes to the advancement of technology by providing a theoretical foundation for new technologies and has applications in various fields such as mathematics, engineering, and biology. It can also be used to solve real-world problems in industries and fields such as software development and natural language processing.
colt
Hi, I would appreciate if someone can check my answers about three questions about computer science and if they are not, what it is missing.

Homework Statement

1)Proof that the following languages aren't regular. You can use the pumping lemma and the closing of the class of the regular languages under union, intersection and complement.

a) {w|w {0,1}* is not a palindrome}

The Attempt at a Solution

My solution: Pick up w as the string 010010. x=empty, y=01 & z=0010. By the pumping lemma the string xyyz should also be regular.
However xyyz=01010010 which is not a palindrome. So, by contradiction, letter a is not a regular language.

Homework Statement

b) {wtw|w,t e {0,1}*}

The Attempt at a Solution

My solution. Pick up w as the string 0101 and pick up t=011 as the other string. So wtw= 0101 011 0101 which belongs to {0,1}By the pumping lemma, the string xyyz should also be regular, However, choosing y=110 of 010 0|11 0|0101, the string 0101 011 110 0101 is produced which cannot be generated by wtw. So, by contradiction, letter b is not a regular language.

Homework Statement

2)Give an counter-example to show that the following contruction fails into proof that class of languages free of context is closed under the operation star. By A a language free of context that it is generated by the GLC G = {V,,R,S}. Add the new rule S -> SS e call the resulting grammar G'. That grammar is expected to generate a*

The Attempt at a Solution

I have only a superficial comprehension, I believe it is necessary that Rg', the set of production rules of G' must be equal to Rg united with {Sg'->SgSg'|e} or in another words Rg': Rg U {Sg'->SgSg'|e}. Even if that it is correct I don't understand why {Sg'->SgSg'|e} is necessary

Homework Statement

3)By A = {(R)|R it is a regular expression that describes a language containing at least a w string that has 111 as a substring (that it is, w=x111y to some x and some y)}. Show that A it is decidible

The Attempt at a Solution

Create a turing machine P, this machine receives a pair <R,W> where R is the regular expression in question and W is the set of all the strings of the form x111y. P converts R into a NFA called NFAR. It sends the pair <NFAR,W> to a TM N that acts as a subrotine of it. N will convert NFAR into a DFA called DFAR. Then inside this machine N, there is a turing machine M inside it, also acting as a subrotine. It sends the pair <DFAR,W> to M. When M receives its input, it will first determines whether it properly represents a DFA DFAR an a set of strings W. If not, it will reject, and as a result, so will N and then P. Otherwise, It will start to simulate DFAR over the first string w(i) of W (where i=0,1,2... n° last input string). If DFAR accepts, M halts in the accept state, and so will N and then P. Otherwise M will continue to looop through all the strings of W. If it reaches the last w(i) and it is not accepted, M will halt in the refect state and so will N and then P.

My fear is that the number of strings to be tested is infinite, so M could enter in a loop?

P.S: I just did a similar topic here http://www.mymathforum.com/viewtopic.php?f=27&t=45768

Thanks for any help

Last edited:
.My solution is correct, but you might want to add more detail about the specific steps of the Turing machine P and its subroutines N and M. For example, how does P convert R into a NFA? How does N convert NFAR into a DFA? How does M simulate DFAR over the first string w(i) of W? You should also mention that since there are only a finite number of strings in W, M cannot enter an infinite loop.

1. What is the difference between computer science theory and computer science practice?

Theoretical computer science focuses on the fundamental principles and concepts that underlie computer science, such as algorithms, data structures, and computation. It is more abstract and mathematical in nature. On the other hand, practical computer science deals with the application of these theories to real-world problems and the development of software and systems. It involves hands-on programming and implementation.

2. What are some of the key areas in computer science theory?

Some key areas in computer science theory include algorithms, automata theory, computability and complexity, data structures, formal languages, and logic. These areas are essential for understanding and analyzing algorithms and systems, as well as for developing new ones.

3. How does computer science theory contribute to the advancement of technology?

Computer science theory provides the theoretical foundation for the development of new technologies and systems. It allows researchers and engineers to understand the limitations and capabilities of computers and algorithms, and to design more efficient and reliable solutions. Many breakthroughs in technology, such as artificial intelligence and cryptography, have been made possible through advancements in computer science theory.

4. Is computer science theory only relevant for computer scientists?

No, computer science theory has applications in various fields, such as mathematics, engineering, and biology. Many mathematical concepts and techniques, such as graph theory and linear algebra, have been applied to computer science theory. In addition, computer science theory has also been used to model biological systems and analyze biological data.

5. Can computer science theory be used to solve real-world problems?

Yes, computer science theory is the foundation for solving real-world problems in various industries and fields. For example, algorithms and data structures are used in software development to improve the efficiency of programs. Formal languages are used in natural language processing to analyze and process human language. Overall, computer science theory provides the tools and methods for solving complex problems in many areas of society.

• 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
5
Views
2K
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
2
Views
4K
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
3
Views
2K
• Engineering and Comp Sci Homework Help
Replies
2
Views
1K
• Math Proof Training and Practice
Replies
114
Views
6K
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K