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

2
votes
1answer
50 views

Show a language is regular with Myhill-Nerode Theorem

I understand how to show a language is not regular using Myhill-Nerode Theorem (proof by contradiction), but how do you show the language is regular? Take language $0^*1^*$ for example. I know this ...
1
vote
1answer
73 views

Random walk in a graph

This is a question about random walk from vertex $s$ in a graph (can be directed), which is defined in the following manner: The random variable $X_0$ (whose possible values is the set of vertices) ...
1
vote
0answers
31 views

Numerically robust computation of the mutual information

Given the numerical distributions $p(x,y), p(x|y), p(y|x)$, what is the most numerically robust way of computing $I(X;Y)$? Should one use the formula for $I(X;Y)$ directly? Or should we use either of ...
-1
votes
2answers
53 views

Unable to meet integration tolerances without reducing the step size below the smallest value

I am solving system of Differential-Algebraic using ODE15s MATLAB, and this is a segment of my code ...
1
vote
0answers
25 views

What does it mean that a Monte Carlo (MC) algorithm is correct with probability at least $p$?

I was trying to understand the definition of what it meant to say that a Monte Carlo (MC) algorithm succeeds with probability at least $p$. Usually in probability I would have concluded that the ...
1
vote
0answers
27 views

Consistency of the SKI calculus as unprovability of S = K

The exercise I'm dealing with asks me to show that by adding $S = K$ to the usual reduction rules for the SKI-calculus, one obtains an inconsistent equivalence. This must be done without using Böhm's ...
1
vote
1answer
35 views

Pumping Lemma for $L=\left\{0^i 1^{j} \mid \gcd(i,j) = 1\right\}$

Let $L=\left\{0^i 1^{j} \mid \gcd(i,j) = 1\right\}$ I want to prove that this is not a regular language, but I am having trouble finding a string I can pump resulting in the string not being in the ...
0
votes
0answers
16 views

Estimating probability (with approximate 95% confidence intervals) in R

How to estimate probability (with approximate 95% confidence intervals) in R programming language ? What is the code ?
2
votes
1answer
22 views

$f,g_1,…,g_k$ computable imply $h(x_1,…,x_n)=f(g_1(x_1,…,x_n),…,g_k(x_1,..,x_n))$ computable. Does the converse hold?

In the book "Computability, complexity and languages" by Davis, Sigal and Weyuker, the following $\bf THEOREM$ If $f,g_1,...,g_k$ are computable functions, then ...
1
vote
0answers
24 views

Intersection automaton of two automata

I need to build the intersection automaton of these two automata My attempt: My attempt is correct?
0
votes
1answer
48 views

chords in a cycle at graph theory

$G=(V,E)$ is undirected graph which follow the rule $\delta(G)\ge3 $ I need to show that it has inside at least one cycle $C$ with at least one chord ($(x,y)$ is a chord of $C$ if $x$,$y$ are indeed ...
1
vote
1answer
28 views

Graph Theory Bipartite graph

If there is a room with 15 women, each woman shakes the hands of 8 men and each man shakes the hands of 6 women, how men there are in the room? So far I wrote this: Women group A=$(v_1...,v_m)$ ...
0
votes
2answers
37 views

Injection from $\mathcal{P}(\{0,1\}^*)$ to $[0,1]$

I'd like to find an injection $\mathcal{P}(\{0,1\}^*)\to[0,1]$. By $\mathcal{P}(\{0,1\}^*)$ I mean the powerset of the set of finite sequences over the numbers $0$ and $1$ and by $[0,1]$ I mean the ...
2
votes
2answers
212 views

An exercise on combinatory logic

Can somebody help me with the following exercise? (1) Find a combinator $X$ such that $Xy = X$; (2) Find a combinator in normal form with the same property. Rules for reduction are $Ix > x$ $Kxy ...
0
votes
2answers
26 views

Center of mass from shape boundary

It is possible to find a shape center of mass by only its boundary? Would the average coordinates of X and Y would approximate my center of mass? (If it would work how good the approximation is going ...
0
votes
0answers
67 views

What is the diameter of Cn and Pn

I need to find for each $3\le n\in N $ what is $C_n$ Diameter and his Complement graph Diameter and the same for each $1\le n\in N $ what is $P_n$ Diameter and his Complement graph Diameter. Here is ...
2
votes
1answer
42 views

Hindley's “Introduction to combinatory logic”, exercise 6 chapter 2.

Can somebody help me with the following exercise? Find a combinator X such that X = S(KK)(XS). Reduction rules are usual: IX reduces to X (identity combinator) KXY reduces to X SXYZ reduces to ...
0
votes
1answer
24 views

Hardest boolean formula circuit complexity upper bound

I have stumbled upon Shannon's result that states that the maximum number of gates in a circuit needed to compute a boolean function on n bits, $f:\{0,1\}^n \to \{0,1\}$, is $\Theta (2^n/n)$. So far ...
0
votes
0answers
14 views

Suppose that CFG G defines $T^*$. Does G defines every language $L$ over the alphabet T?

Suppose that CFG G defines $T^*$. Does G defines every language $L$ over the alphabet T ? Why the answer for this question is false ? G generates every string in the set $T^*$ and if $L$ is a ...
-1
votes
1answer
13 views

Newbie Question formal languages N-1 for a language typ 3

I have the following problem: If I have a Grammar G with (Vn, Vt, P, S) Vn ={S}, Vt = {0} P: S -> 0S S -> 0 Why is the derivation from G: 0^(n-1)S? S => 0S => 00S => ... => 0^(n-1)S => 0^n Is it ...
0
votes
1answer
70 views

An encoding of non - empty sequence of strings

An exercise problem $:$ Let $\Sigma = \left\{a, b, c, d, e\right\}$ be an alphabet. We define an encoding scheme as follows: $g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11$. Let $p_i$ denote ...
2
votes
0answers
26 views

How does one decide if $N = pq$ is prime or not in the special case when $N \equiv 3 \pmod 4$?

I know that there are primality testings that are deterministic but I wanted to know the answer of this question anyways, just for fun. I was trying to design a randomized algorithm that decides ...
0
votes
0answers
30 views

What does it mean “the transition function of FA M is derivable in CFG G”?

I don't understand this question. Let $M$ be a finite automaton. If every production of G is accepted by M and the transition function of $m$ is derivable in G, then $L(G)$ = $L(M) ?$ What does ...
0
votes
2answers
26 views

Is the concatenation of two arbitrary alphabets is considered an alphabet?

Is the concatenation of two arbitrary alphabets is considered an alphabet ? Also Is the set of all Java reserved words is considered an alphabet ? I am inclined to say yes. We could take a string and ...
0
votes
1answer
68 views

Is $P=NP$ an $NP$-complete problem?

Is $P=NP$ an $NP$-complete problem? In other words, is it possible (and does it make any sense) to show that proving $P=NP$ (or $P\neq NP$) cannot be done in polynomial time? I am not even sure it ...
1
vote
0answers
18 views

Determine existence of matroid with some barrier given

Let $E$ be a finite ground set. Let $\mathcal{L}$ (as lower barrier) and $\mathcal{U}$ (upper) be subsets of $2^E$. How can we determine whether there is some matroid $\mathcal{M}=(E,\mathcal{I})$ ...
1
vote
3answers
61 views

Discrete Mathematics - Determine if the following function is onto, one to one or both.

I have a test next week and im going through a sample test. One of the questions involves determining if the function is one-to-one, onto or both. I managed to proof its not one-to-one but am stuck on ...
2
votes
1answer
35 views

A Game of Random Walk plus Combinatorics

1 Original and reasons for this game This game is actually changed from Geoffrey and David's Book [1] (section 11.2, page 445) and its accompanying solution manual [2]. The book gives the result ...
0
votes
1answer
65 views

how to solve this graph theory question?

if G=(A,B,E) is a graph without directions. and (i mean unite value) |A U B| =50 what is the max value of |E| ? im very new at the topic and if there is anywebsite that also can explain more.. it ...
2
votes
0answers
45 views

A recursive problem with GAP concerning lists and an iterator loop

I have the following question concerning a list algorithm in GAP: Let $L_1$ be a non-empty list with certain objects as entries. I wrote a program and called it helping_program_1. The Input for ...
0
votes
1answer
20 views

Pumping lemma for $a^n b^m a^{n+m}$

I want to show that $L = \{a^n b^m a^{n+m} \mid n, m \geq 0\}$ is not regular. Is it suffice to say that $a^0b^pa^p$ is in the language, then y = $a^k$ with 0 < k <= p, choose i = 0 so I get ...
1
vote
1answer
100 views

Mathematical Modeling of Route Optimization

Do any of you know how to come up with equations or mathematical way of representing these problems? 1) Finding probability of choosing number of routes (i) If n of routes less than 4, consider ...
0
votes
1answer
22 views

Calculate bigO notation of recursive relation

I am attempting to calculate the big O notation for a simple recurrence relation $$T(n) = T(n/2) + 1\quad\text{when}\enspace n ≥ 1$$ $$T(1) = 1$$ So my attempt was as follows $$T(n) \le ...
1
vote
1answer
95 views

Give a recursive definition for the set of finite binary strings with an even number of 0s followed by 1s

Give a recursive definition for the set $S$ consisting of finite bit-strings containing an even number of $0$s, and all $0$s (if present) appear before all $1$s. That is, $001\in S$ and $1\in S$, ...
0
votes
0answers
12 views

Minimizing this Boolean Algebra expression

I have the expression... AB'C'D+ABC+AB'D' I completely forget how to do this from Discrete Math, the answer I got was BC in the end but I feel this is wrong. Can someone do this one as an ...
0
votes
0answers
24 views

Using Pumping Lemma to show a language is not regular

Let $$L=\left\{0^n 1^{2n} \mid n > 1\right\}.$$ Show that $L$ is not regular. Attempt: If the language is regular, it must satisfy the Pumping lemma. $P$ will be our pumping length and our string ...
1
vote
0answers
17 views

Finding objects from a list with some properties in $O(n)$

Lets say I have $2$ strings each having $4$ characters. $k$ is a number $\le 4$. If, $2$ strings have exactly $k$ common characters lets say they are a "happy pair" with $k$ points. If I have $n$ ...
0
votes
2answers
26 views

Creating DFA to prove closure properties

I am given a language $L \subseteq \Sigma^*$ and symbol $a \in \Sigma$. Let $a/L= \{ w \in \Sigma^*~|~ wa \in L \}$ ex. String that end in $a$ but with that last $a$ removed. I am trying to prove that ...
0
votes
0answers
23 views

Predict a point when you are given initial measurements

From given (x,y) sensor measurements, output by a robot, I need to find robot's heading direction and predict the next location. I have an algorithm that when programmed gives me the correct answer, ...
1
vote
2answers
77 views

Are we also shifting the mantissa in the fast inverse square root?

I've read this blog about the algorithm: http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/ I understand that we have to manipulate the exponent in order to obtain ...
0
votes
1answer
44 views

Tracking a Robot in circular motion

I have to write a program to predict the location of a robot that's moving in a circle(well, almost circle). I'm getting sensor measurements(they could be with or without noise, both.) from the robot, ...
1
vote
1answer
93 views

Big O with multiple variables ($n,m$): Is $O((n+1)^m) = O(n^m)$?

In the big O notation with multiple variables ($n,m$), is $O((n+1)^m) = O(n^m)$? Details: My intuition said yes, since adding a constant should neither have an effect in big O notation, even in a ...
0
votes
1answer
45 views

Finding the mantissa from binary with floating point numbers?

Here is the example problem slide I am working with: I understand how to get the exponent, its just 2+128=130-127=3 I understand the first bit is the sign bit for positive or negative. I just ...
0
votes
1answer
37 views

Is $L = \left \{ a^m b^mca^nb^m \mid m,n \geq 0 \right \}$ context free language?

I have doubt , regarding this question Is this language is context free ? $L= \left \{ a^m b^mca^nb^m \mid m,n \geq 0 \right \}$ IMO : push all $a$'s , match with $a$ and pop $b$'s ,(now stack ...
1
vote
1answer
33 views

Is $L_1$ context free language?

Let $L = L_1 \cap L_2 $, where $L_1$ and $L_2$ are languages as defined below: $L_1= \left \{ a^m b^mca^nb^m \mid m,n \geq 0 \right \}$ $L_2=\left \{ a^i b^j c^k \mid i,j,k \geq 0 \right \}$ Then L ...
0
votes
1answer
86 views

binary resolution rule proof

I want to proof the binary resolution rule that is, if we For any two clauses $C_1$ and $C_2$, if there is a literal $L_1$ in $C_1$ that is complementary to a literal $L_2$ in $C_2$, then delete $L_1$ ...
0
votes
1answer
13 views

Computer arithmetic - size of error.

I'm actually reading What Every Computer Scientist Should Know About Floating-Points Arithmetics and I have a little problem with understaing one thing. Here's a quote: Write $(b \otimes b) ...
0
votes
0answers
42 views

First fit algorithm for interval graphs for finding proper coloring?

Use the First Fit coloring algorithm to find the chromatic number of the interval graph whose interval representation is shown in intervals here as well as a proper coloring using as few colors as ...
1
vote
0answers
49 views

How to prove a programming language is not Turing complete?

How does one prove that a programming language is not Turing complete? I know one may attempt to show that every program that could be written in the programming language in question is primitive ...
4
votes
0answers
73 views

Best sources on complete transforms (classic orthonormal transforms) and overcomplete transforms in signal processing

In the introduction section of a thesis I read a little about classic orthonormal transforms such as Fourier, discrete cosine and wavelet transforms and their application in signal processing. Then ...