Most voted "computer-theory" questions
36 questions
Sort by count of
-
108
votes13
answers20263
viewsWhat makes a language to be considered low/high level?
What makes a language to be considered high-level and other low-level?
-
78
votes2
answers35446
viewsWhat is the complexity of an algorithm?
What is the complexity of an algorithm? And what are the ways to measure it? (Big O, Big Theta...)
-
53
votes4
answers2561
viewsWhat’s wrong with gluttonous philosophers?
When it comes to concurrent programming, they always mention 3 classic problems/competition models: producers and consumers readers and writers glutton philosophers (or dinner of philosophers) I…
-
46
votes2
answers3637
viewsThe first programming language
Until the time when computers were purely mechanics and were programmed by punch cards I understand how it works. Later, when the first "digital" computers operated with valves and relays appeared,…
assembly compilers language-design computer-theoryasked 7 years, 12 months ago Michael Pacheco 1,657 -
44
votes2
answers2825
viewsWhat is a Turing stop problem?
I’ve read and reread on Wikipedia, I’ve watched some 15 videos in English and Portuguese on this subject, I’ve read several articles on google, but I can’t understand. Why would she go into an…
-
31
votes2
answers5048
viewsWhat is a context-free language?
In Wikipedia has the following statement: In formal language theory, a context-free language (LLC) is a language generated by some context-free grammar (GLC). Different context-free grammars can…
terminology computer-science computer-theory formal-languagesasked 7 years, 8 months ago viana 27,141 -
27
votes1
answer2607
viewsWhat are the main differences between a quantum computer and a conventional computer?
They say quantum computing will revolutionize computation if it is implemented successfully. Why is that? What are the main differences between a quantum computer and a conventional computer that…
computer-theoryasked 9 years, 9 months ago Carlos Cinelli 16,826 -
23
votes1
answer1194
viewsRegular expression to recognize language: words that do not contain "bbab"
The @LINQ challenged me to write a regular expression to recognize the following language L: I was able to assemble, on this premise, the following finite state machine: the Miguel Angelo detected a…
regex mathematics computer-theory automata formal-languagesasked 7 years ago Jefferson Quesado 22,370 -
23
votes1
answer583
viewsWhat is the complexity class NPI?
Studying complexity, I came across the term NPI. It means NP-intermediate. But I didn’t understand what this "intermediary is". What characterizes an NPI problem? Why does it have that name? There…
-
17
votes2
answers809
viewsWhat will the new logic of quantum computer programming look like?
There is a lot of talk about quantum computers with high performance and processing capacity. Unlike bits, the qubits of quantum computers, working with superposition, can assume three different…
algorithm compilation binary computer-science computer-theoryasked 8 years, 11 months ago Denis Caixeta 3,427 -
16
votes3
answers651
viewsProblem of stopping can be solved in practice?
The halting problem can be explained as: given a program and an input for it, it will complete its execution and return a response or will enter an infinite cycle? This has been proved undecidable…
computer-theoryasked 10 years, 1 month ago Guilherme Bernal 20,024 -
15
votes2
answers4859
viewsWhat is von Neumann’s architecture?
How it works and why it has become the dominant computer model?
memory computer-science architecture-computers computer-theoryasked 7 years, 6 months ago Marcell Alves 2,453 -
15
votes1
answer229
viewsIs a finite state machine capable of detecting the primality of a number?
I recently saw a publishing how they taught Perl to recognize a prime number using regular expressions. The regular expression in question is: /^1?$|^(11+?)\1+$/ The only requirement of this regular…
regex mathematics computer-theory automata formal-languagesasked 4 years, 7 months ago Jefferson Quesado 22,370 -
14
votes2
answers3574
viewsWhy is set theory so important to computation?
For computer theory, formal languages among other areas as well as for programming (development) set theory is always present, I know that mathematics is strongly linked to computation, but why do…
-
13
votes1
answer28267
viewsWhat is the Turing machine?
What is this such Máquina de Turing that made Turing be recognized as the "Pai da Computação"? How it works and how it reads a binary tape?
computer-theoryasked 7 years, 11 months ago guijob 1,809 -
11
votes4
answers584
viewsHow to verify the efficiency of these 2 functions in C++?
How to determine the best choice between these two functions for implementation? 1: int X(int x){ if(x<=0) return 0; return(x + X(x-1)); } 2: int Y(int x){ int soma=0; for(int i=0;i<=x;++i)…
-
8
votes2
answers218
viewsCould someone help me with this formal language?
Could someone help me with the following language: {a^n b^m | n<= m <= 2n} Forgive my ignorance, but I’m failing to form a battery automaton with this language. I’m trying through a…
computer-theoryasked 7 years, 4 months ago Breno Lima 81 -
8
votes1
answer1301
viewsWhat is Harvard architecture?
Reading a few things about architecture, in several cases it is compared to Harvard Architecture with Von Neumann Architecture. I found here in the SO this question about What is von Neumann’s…
-
7
votes2
answers1021
viewsWhat is a decision problem?
I started reading about computer theory and came across the "decision problems". What are these problems? I don’t want any highly elaborate scientific article to answer the question, just a quick…
-
6
votes2
answers4614
viewsCharacter size (ASCII vs other encodings) in bytes
Seeing this issue a doubt arose, coming from PHP and in the past having "problems" derived from character encoding, ex: srtpos vs mb_strpos, i knew that all ASCII characters have 1 byte, but I…
-
6
votes1
answer213
viewsWhat is the architecture of Cleopatra?
There are several basic modern computer architectures. Here at Sopt has some questions, about von Neumann architecture and harvard. Recently, in a small reading, they cited another architecture,…
-
6
votes1
answer66
viewsA subset language of a context-free language is decidable?
If we have a context-free language L and L' is a subset of L, then L' is decidable?
-
5
votes1
answer425
viewsWhat is the Pumping Lemma (or Pumping Lemma) ? And how to apply it?
I was reading by HOPCROFT and had difficulty applying the pumping lemma in a formal way to exercises to prove that a language is not regular. In this case, I refer to the Pumping Motto for regular…
-
5
votes1
answer1014
viewsDifference between 'Regular language' for 'irregular language'
Reading a question about basic programming concepts, I come across the following statement: Let A and B be two languages over the binary alphabet, that is, over the alphabet composed only of 0’s and…
computer-science computer-theory automata formal-languagesasked 5 years, 8 months ago Luiz Augusto 2,482 -
4
votes1
answer326
viewsReduce grammars in the Chomsky hierarchy
I know from Chomsky’s hierarchy, all regular grammar is also a context-free grammar. Similarly, I know that a context-free grammar is also a context-sensitive grammar and etc. I’d like to know how…
-
4
votes1
answer5505
viewsWhat is starvation (starvation)?
Some conditions may prevent progress in the execution of processes or threads, two of these conditions are called dead-lock and live-lock, where what I extracted from information was that, dead-lock…
-
3
votes1
answer460
viewsWhat are the differences between the computational power of deterministic and non-deterministic stack automata?
There is computational power difference between a deterministic stack automaton and a non-deterministic automaton?
-
3
votes1
answer775
viewsDoubt about Chomsky’s hierarchy
Regarding the 4 types of languages, I doubt to understand about context-dependent or context-sensitive language. I find very confusing the explanation that I find through the sites, I would like…
-
3
votes1
answer1775
viewsHow to turn a context-free grammar into a stack automaton?
I have a grammar, like for example: Or else: Or even that: Or this grammar, which represents the boolean logic for three variables: How to turn these grammars into stack automata? Would have some…
algorithm computer-theory automata formal-languagesasked 6 years, 11 months ago Jefferson Quesado 22,370 -
3
votes0
answers98
viewsNowadays.. How far does the front end go?
before marking as duplicate of the following question Difference between client-side and server-side. Let’s look at some facts. The previous question is from 2013 or 4 years ago, long before the…
-
2
votes1
answer60
viewsParser Generator and Transpilator what’s the difference?
While studying about compiler types I came across the term: Source-to-Source concerning the procedure for transpilation. It turns out that some sections further down the term Parser-Generator and…
-
1
votes1
answer159
viewsAre there paradoxes in computing?
There are some paradoxes in Electronics and other areas of knowledge and this question has appeared in this field.
computer-theoryasked 7 years, 5 months ago user1084 -
1
votes2
answers167
viewsHow to limit a function parameter so that it is an element of a set?
My intention is to define a function that allows to simulate the execution of a deterministic finite automaton (DFA) datum. According to the formal definition a DFA is the 5-upla M = (Q, Σ, δ, q0,…
-
1
votes1
answer297
viewsConcepts for the adoption of object orientation
I came across this question, researched it and the correct answer is: e) computing is triggered by the exchange of messages between objects. I agree that the And is true, but what I don’t understand…
-
1
votes2
answers57
viewsWhat is the correct definition of concatenation and what really happens when we do this with variables?
I’m learning programming on my own and I confess I’m still at the beginning. Using Portugol Studio, I learned a little about concatenation and, at first, it seemed simple. The initial concept given…
-
0
votes1
answer87
viewsWhat is the difference between the complexity of an algorithm and the complexity of a problem?
I would like to know the difference between the complexity of an algorithm and the complexity of a problem, that is, which points differ the two things
computer-theoryasked 7 years, 3 months ago Leomar de Souza 1,074