All mathematical questions about computer science, including theoretical computer science, formal methods, verification, and artificial intelligence. For questions about Turing computability, please use the (computability) tag instead. For numerical analysis, use the (numerical-methods) tag. For ...

learn more… | top users | synonyms

1
vote
2answers
164 views

Sequences of a computable function

Is there any computable function $f(n)$, which given any integer $n$ has been proven to return either $0$ or $1$ in finite time, and for which the statement "$f(1), f(2), f(3),\ldots$ contains ...
19
votes
4answers
2k views

Is chess Turing-complete?

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff ...
1
vote
0answers
568 views

Regular expression from DFA

I want to create a regular expression from the following deterministic finite automaton using an equivalence system: $\begin{align}L_1 = & \{a\}L_1 &\cup& \{b\} L_2 & \cup & \...
3
votes
1answer
83 views

Equivalences of regular expressions - which one is wrong?

Let $\alpha,\beta \in \text{RA}(\left\{0\right\})$ where $RA(\Sigma)$ is the set of all regular expressions of the alphabet $\Sigma$. The following two equivalences are given: $\alpha\...
1
vote
1answer
165 views

Reduction over intersection of languages

Given two languages $L1$ and $L2$, such that $L2$ is NP-Hard under polytime (many-one or Turing) reduction. Let $L=L1\cap L2$. 1- Is it true that if $L2$ is polytime (many-one or Turing) reducible to ...
25
votes
1answer
657 views

Always oddly-many ones in the binary expression for $10^{10^{n}}$?

Update: Pending independent verification, the answer to the title question is "no", according to a computation of $q(10) = 11609679812$ (which is even). Let $q(n)$ be the number of ones in the ...
0
votes
2answers
116 views

What (formal) language does this describe? And, how do I prove it's regular?

I have this problem that I can't seem to be able to wrap my head around, and I was wondering if there was someone here that could help me understand it. Let $L_1$ be a regular language over $\{a, b, ...
3
votes
2answers
574 views

Time complexity of sorting a partially sorted list

Assume a sorted list of $n$ elements followed by $f(n)$ elements in random order. How would you sort the whole list given the following: a) $f(n)=O(1)$ b) $f(n)=O(\log n)$ c) $f(n)=O(n^{1/2})$ d) ...
3
votes
1answer
156 views

How to intercept someone moving in a 2-dimensional grid world?

Suppose you have a discrete 2D grid where each point represents a person, for example $\mathbf{d} = (x_d, y_d)$. Each person can only move exactly one square up, left, right or down (or stay put) per ...
0
votes
1answer
201 views

inverse polynomial

I am reading from some notes on cryptography and came across this sentence: "We call a function f negligible in k if it asymptotically approaches zero faster than any inverse polynomial in k i.e., $f(...
0
votes
1answer
322 views

Comp Sci Math; Hamming Distance

I've been tasked with this question but I have no idea how to answer it. What is the maximum possible hamming distance between two points from level i in a n-cube?
3
votes
1answer
607 views

Directed Graph, shortest path algorithm. I don't even understand what this question is asking. Is it a trick question or just Dijkstra's?

Consider a directed graph with each edge assigned a nonnegative weight D that reflects the difficulty of passing over that edge (perhaps modeling an obstacle course). Define the difficulty of a ...
2
votes
1answer
267 views

Need to express curves as a set of gaussians, and compare two of these sets

I have two xy curves, defined numerically on a given (potentially different) range of x coordinates. What I need to do is to compare these two curves with the following strategy: express each curve ...
6
votes
1answer
1k views

What about Genetic Algorithms from a mathematical point of view?

Last year I've attended an Artificial Intelligence course (it was very simple, just a summary of the main ideas); we've seen what a genetic algorithm is and the idea seems very interesting to me. Now ...
7
votes
2answers
3k views

Advice for how to learn more advanced math for audio signal processing?

I am very interested in learning about audio from a signal processing standpoint. However, whenever I try to further my education by reading books, I get extremely frustrated because the books use ...
1
vote
2answers
421 views

How do I generate the set of binary strings with elements that are unique under reversal?

What is the most efficient way to generate the set $S$ of unique binary strings of a certain length, $L$, s.t. all strings are unique under the reversal operation? For example, if $L = 2$, the ...
2
votes
1answer
1k views

CRC computation

I would like to understand the CRC computation using CCITT CRC-16 $x^{16} + x^{12} +x^{5} +1$. I was able to successfully implement it in a program but I would like to understand the computation ...
2
votes
4answers
162 views

Regular expression $baa \in a^*b^*a^*b^*$: is that true or false?

Could someone please guide me how to go about solving this problem? $$ baa \in a^*b^*a^*b^* .$$ The question asks whether string $baa$ is an element of $a^*b^*a^*b^*$ (in other words a set of any ...
2
votes
1answer
248 views

Where to find $\lambda$-calculus examples? For instance, how to check if a list is empty?

I'm trying to remove many layers of dust from my knowledge about $\lambda$-calculus, without my notes from classes (several hundreds of km and 5 years away). I was trying to understand the examples ...
4
votes
1answer
720 views

Order of growth proofs?

I was wondering how people go about showing the proofs with orders of growth? Currently, I have the following functions and I know what order they go in, but I'm not sure how to prove them. I simply ...
2
votes
1answer
764 views

Unable to construct Context-free Grammar from Pushdown Automaton

I have a problem in constructing a Context-free Grammar for the Language $$L = \{a^mb^n : m≠n,m>0,n>0\} .$$ Though I can able to construct a Pushdown Automata. I can construct a CFG, but it ...
2
votes
3answers
364 views

Math/CS Algorithm Analysis Question

I've placed this on the Math Stack Exchange even though it is really a CS question because it is the math that is stumping me. Please note, I'm not asking you to do this problem for me, just to make ...
1
vote
1answer
197 views

which class does this function belong to in the fast growing hierarchy?

the class $\mathfrak{F}_k$ of the fast growing hierarchy is the closure under substitution and limited recursion of the constant, sum,projections and $F_n$ functions for $n\leq k,$where $F_n$ is ...
4
votes
2answers
492 views

Formally verifying that $n \log n = o(n^2)$

I am trying to verify that $n \log n = o(n^2)$ using the formal definition of small-o. The definition of small-o is as follows Let $f$ and $g$ be functions $f,g: \mathbb{N} \rightarrow \mathbb R^+...
5
votes
2answers
445 views

Regular Expression question

Notepad++ has a "regular expression" search but it does not implement the pipe OR | operator, which allows you to take two regular expressions and union them into ...
16
votes
4answers
11k views

Do dynamic programming and greedy algorithms solve the same type of problems?

I wonder if dynamic programming and greedy algorithms solve the same type of problems, either accurately or approximately? Specifically, As far as I know, the type of problems that dynamic ...
1
vote
1answer
237 views

About a ordinal-based definition of fast-growing functions

I try to understand the Löb-Wainer-hierarchy and one definition just doesn't open. I hope someone could clarify this to me. A fundamental sequence to limit ordinal $\alpha$ is $\omega$-sequence $\{\...
2
votes
1answer
286 views

Optimizing a string to have the shortest possible unique substrings

I would like to construct a length $N$ string over a $k$-letter alphabet, $S$, such that any substring of $P$ sequential characters in $S$ is unique for as small a value of $P$ as possible. To ...
2
votes
0answers
234 views

Further question on “uncountable” Turing Machine

Having read An "uncountable" Turing Machine? I have further questions that I don't believe it addressed. (I'm a programmer, not a mathematician so I apologize if this is stupid or the ...
6
votes
2answers
2k views

How to determine if it's possible to draw a graph $G$ with a given set of vertices?

Given a list of vertices associated with its degree, says: $$7, 7, 3, 3, 3, 3, 3, 1$$ Determine whether it is possible to draw a graph $G$, where $G$ is connected and un-directed. Solution: The ...
13
votes
3answers
653 views

Curious Properties of 33

Because my explanation has so many words, I'll start with my question and then you can read the explanation if you need to: The Bernstein Hash method uses the number 33 as a multiplier. From what I'...
-1
votes
1answer
1k views

how random is ( rand() > rand() ? true : false )

I was going to post this question on SO but I suspect it needs mathematical treatment. I need to make a decision(True or False) while running a simulation and I decided that this particular decision ...
2
votes
2answers
616 views

Analysis of algorithms and recurrence relations

Suppose that the function of the time of execution of some recursive algorithm is given by a recurrence relation of order $n$. Let $$p(x)=0,$$ with $p(x)$ a polynomial of degree $n$, the corresponding ...
2
votes
1answer
977 views

Construct PDA that accepts the language $L = \{w_1cw_2 : w_1, w_2 \in \{a, b\}^*, w_1 \neq w_2^R\}$

Problem Construct PDA that accepts the language $L = \{w_1cw_2 : w_1, w_2 \in \{a, b\}^*, w_1 \neq w_2^R\}$ For the language $wcw^R$, it's much easier because the stack is always empty after ...
2
votes
2answers
4k views

Construct PDA that accepts the language $L = \{ a^nb^{n + m}c^{m}: n \geq 0, m \geq 1 \}$

Problem Construct PDA that accepts the language $L = \{ a^nb^{n + m}c^{m}: n \geq 0, m \geq 1 \}$ My initial idea was, If we read an $a$ push a $x$ onto stack If we read a $b$, there are two ...
4
votes
1answer
1k views

Question regarding stack operation notation in PDA

I'm currently reading two books: An Introduction to Formal Languages and Automata, 4th Edition by Peter Linz. Introduction to the Theory of Computation, 2nd Edition by Michael Sipser. What ...
8
votes
3answers
1k views

Karatsuba vs. Schönhage-Strassen for multiplication of polynomials

I am wondering how to most effectively multiply two polynomials with several $100$'s of coefficients, each coefficient having $1000$-$2000$ decimal digits. I know Schönhage-Strassen begins to ...
1
vote
1answer
291 views

Question regarding the initial stack symbol in Push Down Automaton

Let $L = \{a^nb^n : n \geq 0\} \cup \{a\}$, where $\Gamma = x, \$, \Sigma = {a, b}$, we have the NPDA of $L$ in three states: In the above state diagram, I can break the transtion $\lambda, \lambda ...
4
votes
3answers
1k views

What is the CFG of the language that generates all strings over alphabet $\{a, b, c\}$?

The most obvious one that I found was, $$S \rightarrow SSS | A | B | C$$ $$A \rightarrow Aa | \epsilon$$ $$B \rightarrow Bb | \epsilon$$ $$C \rightarrow Cc | \epsilon$$ However, I realize this CFG is ...
2
votes
3answers
12k views

Question regarding Context Free Grammar exercises

I'm working on the exercises in "An Introduction to Formal Languages and Automata" 4th Ed textbook by Peter Linz. Since there are too few answers given in the back of the book, I wasn't able to check ...
0
votes
2answers
119 views

Finding a sequence that has special properties

let $n \in \mathbb{N}$. Is is possible to find a sequence $S = \{ s_1, \dots, s_{n+k} \}$ ($k \leq n$) with a polynomial algorithm, so that for every pair $(x,y) \in S \times S$, the products $x \cdot ...
1
vote
2answers
328 views

Pumping Lemma for inequalities

I have decided to teach myself formal languages and so I bought Peter Linz's Formal Languages and Automata. He presents the following problem (and many similar ones) in chapter 8 section 1, and I ...
1
vote
3answers
291 views

Do these two regular expressions $(a + b)^*$ and $(b^*a^*)^*$ generate the same language?

Are the languages generated by the regular expressions $(a + b)^*$ and $(b^*a^*)^*$ the same language? The solution for this problem is yes, but I couldn't figure out why it is true. The first ...
1
vote
1answer
2k views

crack RSA: NP, or NP-complete?

I've heard differing opinions/statements of fact from different professors and sources as to whether cracking RSA is "thought" to be in NP, or known to be an NP-complete problem. Can anyone shed light ...
3
votes
1answer
1k views

Is the language $L = \{a^ib^jc^kd^l : i,j,k,l \geq 0 \text{ and } i + k = j + l\}$ context free language?

Is the language $L = \{a^ib^jc^kd^l : i,j,k,l \geq 0 \text{ and } i + k = j + l\}$ context free language? My initial thought was to prove that it is not a CFL by using Pumping Lemma for CFG with the ...
1
vote
1answer
146 views

basic question about simulating Turing machines with larger alphabets

I'm trying to understand the proof of the time hierarchy theorem appearing in sipser's book. The proof requires a TM M to simulate an arbitrary TM N without too much slowdown. In particular it is ...
3
votes
3answers
935 views

Is the language of all strings over the alphabet “a,b,c” with the same number of substrings “ab” & “ba” regular?

Is the language of all strings over the alphabet "a,b,c" with the same number of substrings "ab" & "ba" regular? I believe the answer is NO, but it is hard to make a formal demonstration of it, ...
8
votes
1answer
855 views

Recognizing and Using Chaitin's Constant

As far as I understand, Chaitin's constant is the probability that a given universal Turing machine will halt on a random program. I understand that Chaitin's constant is not computable--if it were, ...
5
votes
1answer
751 views

Max-turn hamiltonian path in square grids

Given an $n \times n$ square grid graph, what is the maximum number of turns a Hamiltonian path can take?
2
votes
2answers
773 views

Is the language $L = \{0^m1^n: m \neq n - 1 \}$ context free?

Consider the language: $L = \{0^m1^n : m \neq n - 1 \}$ where $m, n \geq 0$ I tried for hours and hours but couldn't find its context free grammar. I was stuck with a rule which can check on the ...