Problem Detail: In class, we were given the following problem: We are given a directed graph G = (V, E) on which each edge (u, v) ∈ E has an associated value r(u, v) which is a real number in the Read More …
Category: Uncategorized
[Solved]: Finding a way out of a polygon
Problem Detail: There is a simply-connected polygon $C$. It contains $n$ pairwise-interior-disjoint simply-connected polygons, $D_1,dots,D_n$: The goal is to select one of the polygons, say $D_i$, and attach to it a polygon $E_i$ such that: $D_icup E_i$ is still simply-connected. $E_i$ Read More …
[Solved]: design of self-loops and final states in fsm
Problem Detail: I am learning about automata and finite state machines. Consider the following automaton, that accepts the word ‘ab’, does not have to be infinite, just once: alphabet: ‘a’,’b’ states: 1,2, 3 (3 is the final state and 1 is Read More …
[Solved]: Best pathfinding algorithm for undirected unweighted graph
Problem Detail: I have an unweighted undirected graph with every node connected with an average of two hundred other nodes (nodes are people from social network). What will be the fastest algorithm to find the shortest path from one node to Read More …
[Solved]: How many languages exist with input alphabet {0,1} and all strings in the language have length less than or equal to 5?
Problem Detail: I’m trying to write a formal proof in automata theory to show a few properties of DFAs but I am having some trouble with this that I am trying to incorporate into my proof. I want to show how Read More …
[Solved]: Finding all paths with lengths in a fixed interval in sparse graphs
Problem Detail: What is the most efficient way to find all paths of length M to N in a large sparse graph? Some general information: Graph has 30,000 to 50,000 nodes Average number of edges per node ~ 10 M=4, N=7 Read More …
[Solved]: Confluence proof for a simple rewriting system
Problem Detail: Assume we have a simple language that consists of the terms: $mathtt{true}$ $mathtt{false}$ if $t_1,t_2,t_3$ are terms then so is $mathtt{if}: t_1 :mathtt{then}: t_2 :mathtt{else}: t_3$ Now assume the following logical evaluation rules: $$ begin{gather*} dfrac{} {mathtt{if}: mathtt{true} :mathtt{then}: Read More …
[Solved]: Intersection of Turing-recognizable language and regular language
Problem Detail: True or false: An intersection of a Turing-recognizable and a regular language is always Turing-decidable. This was asked on a practice test and the answer is False. Why? I thought regular languages were a subset of decidable languages. So Read More …
[Solved]: Problem with storing an existing triangulation in a DCEL
Problem Detail: I am new to StackExchange, and I already made the mistake of posting a new question as a response to a previous question. Here, I rewrote my question more clearly and separately. I am trying to store an existing Read More …
[Solved]: Proving that non-regular languages are closed under concatenation
Problem Detail: How can I prove that non-regular languages are closed under concatenation using only the non-regularity of $L={a^nb^n|nge1}$ ? Asked By : TT8 Answered By : David Richerby You can’t prove it because it isn’t true: the class of non-regular languages isn’t Read More …
