Question about machine epsilon

I am studying over my notes, and there is something I don’t understand about $ e_m$ . We represent the floating point numbers as $ 1.d_1d_2…d_t \times \beta^e$ . Now, my professor defines $ \epsilon_m$ as the smallest $ x$ such that $ fl(1+x) > 1$ . But then she writes

$ $ \epsilon_m = \beta^{1-t} \hspace{1cm} \text{ (for “chopping”)}$ $ and

$ $ e_m = \dfrac 12 \beta^{1-t} \hspace{1cm} \text{ (for rounding)}$ $ However, I think these should be $ \beta^{-t}$ and $ \dfrac 12 \beta^{-t}$ , respectively.

The number $ 1$ , and the next number right after, are

$ $ 1.00 \cdots 00 \times \beta^0$ $ and $ $ 1.00 \cdots 01 \times \beta^0$ $ where the $ 1$ is in the $ t^{th}$ decimal place. Therefore their difference is $ \beta^{-t}$ so if $ x = \beta^{-t}$ , then $ 1+x$ is itself a floating point number, so $ fl(1+x) = 1+x>1$ .

Am I wrong, or are the notes wrong?

Thank you very much.

Let M be an $\epsilon$-NFA and let $S\subseteq Q$. Prove $\epsilon (S) = \epsilon (\epsilon (S))$


Let M be an $ \epsilon$ -NFA and let $ S\subseteq Q$ . Prove $ \epsilon (S)= \epsilon (\epsilon (S))$ .

I would like to prove this by contradiction but I don’t know if my idea is correct.

Definition of $ \epsilon -closure$ : $ \epsilon : 2^Q \rightarrow 2^Q $

a) $ S \subseteq \epsilon (S)$ Base case

b) If $ q \in \epsilon (S)$ then $ \delta(q,\epsilon )\subseteq \epsilon (S)$ Recursive case

c) and nothing else is in $ \epsilon (S)$

Prove i) That $ \epsilon (S) \subseteq \epsilon (\epsilon (S))$ .

By contradiction, suppose $ \exists x \in \epsilon (S)$ such that $ x \notin \epsilon (\epsilon (S))$ .

Using definitions of $ \epsilon (S)$ , we know $ S \in \epsilon (S)$ . So $ x \in S \in \epsilon (S)$ , and $ \delta(x,\epsilon ) \subseteq \epsilon (S)$ .

Using definitions again, we know $ S \in \epsilon (S)$ , so $ x \notin \epsilon (\epsilon (S))\notin \epsilon (S)$ . Also $ \delta (x, \epsilon) \nsubseteq \epsilon (\epsilon (S))$

We have a contradiction because $ x \notin \epsilon (S)$ and we said $ x \in \epsilon (S)$ .

Therefore i) is true.

Show that $L:=\{(a^{k}b)^{i}|i,k \epsilon \mathbb{N}_{+} \}$ is context-sensitve. (With context-sensitive/noncontracting grammar)

I am studying for an upcoming exam and this is an old exam question from two years ago (all exams were made available through our lecturer):

Show that $ L:=\{(a^{k}b)^{i}|i,k \epsilon \mathbb{N}_{+} \}$ is context-sensitve.

I could easily construct a LBA for this language. But since the notation/construction of LBAs weren’t really explained, I would have to define it in the exam.

So I assume this task was expected to be done by constructing a context-sensitive grammar.

NOTE: In our lecture the definition of a context-sensitive grammar was in fact the definition of a noncontracting grammar. So any rule like this x -> y is allowed if |x| <= |y|

So this is allowed:

aAb -> bXaa 

My best idea goes like this:

S  -> AB B  -> bB | b A  -> CA | C Cb -> abC Ca -> aC 

so to generate aaabaaabaaab I do this:

S AB AbB AbbB Abbb CAbbb CCAbbb CCCbbb (let all C-Variables run through the word and leave an 'a' before every 'b') CCabCbb CCababCb CCabababC ... aaabaaabaaabCCC 

But I can’t make all the ‘C’-Variables disappear.

Handling epsilon productions in recursive descent parsing

I am working on a recursive descent parser for lambda calculus. In my grammar, after removing left-recursion, I am left with the following two productions:

# APPLICATION  -> ATOM APPLICATION' # APPLICATION' -> ATOM APPLICATION' | ε        

Both APPLICATION and APPLICATION’ correspond to the same type of node in the AST. How should I handle parsing the second production? I know that choosing between two alternatives for a production is performed by looking up the next token in buffer, but the epsilon production confuses me.

EDIT:

Here is current implementation (Ruby) that fails to left-associate applications.

require_relative 'token.rb' require_relative 'ast.rb'  class Parser     def self.call(tokens)         new(tokens).send(:parse_expr)     end      def self.to_proc         method(:call).to_proc     end      private         def initialize(tokens)             @tokens = tokens             @l = -1         end          def parse_expr             if lookahead.type == :tklambda                 return ExprNode.new([parse_abstraction], @l)             else                 return ExprNode.new([parse_application], @l)             end         end          def parse_abstraction             match_token(:tklambda)             id = parse_identifier             match_token(:tkdot)             expr = parse_expr             return AbstrNode.new([id, expr], @l)         end          def parse_identifier             id_token = match_token(:tkid)             val = id_token.value             return IdNode.new(nil, @l, val)         end          def parse_application             left_child = parse_atom             first_atom = [:tklparen, :tkid] # FIRST(ATOM)             # application -> atom application'             while !lookahead.nil? and first_atom.include?(lookahead.type)                 return AppNode.new([left_child, parse_application], @l)             end             # application' -> atom application' | ε             return left_child         end          def parse_atom             if lookahead.type == :tklparen                 match_token(:tklparen)                 expr = parse_expr                 match_token(:tkrparen)                 return AtomNode.new([expr], @l)             else                 return AtomNode.new([parse_identifier], @l)             end         end          def match_token(type = nil)             if !type.nil? and lookahead.type != type                 raise "Unexpected token at #{@l + 1}. Expected: #{type}, "\                       "got: #{lookahead.type}."             end             @l += 1             return @tokens[@l]         end          def lookahead             return @tokens[@l + 1]         end end 

Asymptotic Bound on Minimum Epsilon Cover of Arbitrary Manifolds

Let $ M \subset \mathbb{R}^d$ be a compact smooth $ k$ -dimensional manifold embedded in $ \mathbb{R}^d$ . Let $ \mathcal{N}(\epsilon)$ denote the size of the minimum $ \epsilon$ cover $ P$ of $ M$ ; that is for every point $ x \in M$ there exists a $ p \in P$ such that $ \| x – p\|_{2}$ .

Is it the case that $ \mathcal{N}(\epsilon) \in \Theta\left(\frac{1}{\epsilon^k}\right)$ ? If so, is there a reference?

Proving equivalence between $\epsilon$ based & $lub$ definition of supremum.

Based on $ \epsilon$ have a new definition of supremum:

Let there be a nonempty set $ X$ with supremum $ s$ , then $ X\cap(s – \epsilon, s]\ne \emptyset, \,\, \forall \epsilon\gt 0$ .

The conventional definition is given by:

Let $ X$ be a nonempty set of real numbers. The number $ s$ is called the supremum of $ X$ if $ s$ is an upper bound of $ X$ and $ s \le y$ for every upper bound of $ X$ .

Let, the conventional definition be denoted by ‘Def. 1’, while the new definition by ‘Def. 2’.

Have two questions below. I need help in attempting them.

Q. 1 : Need show that the two definitions are equivalent by proving the following two conditional statements:

(i) If $ s = sup(X)$ , as given by Defn. 1, then $ s$ is the supremum, as given by Defn. 2. Here, assume that Defn. 1 holds, and use this assumption to prove that Defn. 2 holds.

Let $ s’$ is supremum as per Defn. 2. Also, the relation between the magnitudes of $ s,s’$ is unknown, & need be established.

$ s$ will have set $ X$ elements in the range $ (s-\epsilon, s]$ if $ s-s’ \lt \epsilon$ , by the below proof:

Let us assume that $ s-s’ \ne 0 $ , let $ s-s’=k.\epsilon, k\lt 1$ , then $ s = s’+k.\epsilon \implies s -\epsilon = s’+(k-1).\epsilon \implies s -\epsilon \lt s’$ .

$ s-\epsilon\lt s’\implies \exists x \in X: X\cap (s – \epsilon, s]\ne \emptyset$ .
But, Def. 2 can take any $ \epsilon\gt 0$ to ensure $ \exists x \in X: X\cap (s’ – \epsilon, s’]\ne \emptyset$ .
So, if Def. 1 is to have ability to take any $ \epsilon\gt 0$ , need the lower bound of $ (s – \epsilon, s]$ to equal at least to $ s’ – \epsilon$ .
But, $ s – \epsilon= s’+(k-1)\epsilon \ge s- \epsilon, \forall k, 0\lt k\lt 1$ .
So, the only possible value is $ k=0$ to have the lower bound of $ (s – \epsilon, s]$ equal to $ s’ – \epsilon$ .

But, by this cannot impose any restriction on the upper bound $ s$ (of Def. 1) to equal $ s’$ (of Def. 2).

(ii) If $ s = sup(X)$ , as given by Defn. 2, then $ s$ is the supremum, as given by Defn. 1. Here, assume that Defn. 2 holds, and use this assumption to prove that Defn. 1 holds.

Let us modify for consistency with part (i) sake, $ s$ replaced by $ s’$ .

If Defn. 2 holds, then the upper bound of the interval is bounded by $ s’$ , which is also the last element that can possibly be (if, $ s’\in X$ ) in $ X$ . For Defn. 1 to hold, the upper bound must then be the same as the upper bound of Defn. 2, i.e. $ s’$ .

Q. 2: What is the practical significance of showing that these two definitions are logically equivalent?

The step (i) of showing that if Defn. 1 holds, then Defn. 2 holds, leads to having the lower bound of $ (s – \epsilon, s]=s’ – \epsilon$ .

The step (ii) of showing that if Defn. 2 holds, then Defn. 1 holds, leads to having the upper bound of $ (s – \epsilon, s]=s’$ per bound implies the max. value is $ s=1$ at $ n= \infty$ . All possible values of $ n$ are covered in the interval $ (s-\epsilon,s]$ with $ n=\infty$ at the upper bound.

Proving there is an eigenvalue $\lambda$ for which $|\lambda – b_{jj}| < \epsilon \sqrt{n}$


Let $ A$ be an $ n\times n$ real symmetric matrix. By applying Jacobi’s method, suppose we have generated an orthogonal matrix $ R$ and a symmetric matrix $ B$ such that the equality

$ $ B = R^{T}AR $ $

holds. Moreover, suppose the inequality $ |b_{ij}| < \epsilon$ holds for all $ i \neq j$ .

Show that for each $ j = 1, 2, \ldots, n$ , there is at least one eigenvalue $ \lambda$ of $ A$ such that $ |\lambda – b_{jj}| < \epsilon \sqrt{n}$ holds.


This is an exercise that I am doing to study for my final exam. So, I’ve just recently learned Jacobi’s method, and I know that the eigenvalues and eigenvectors are related to the matrices $ B$ and $ R$ ; however, I have no idea how to use those results to prove an inequality. I also have no idea how to get the $ \sqrt{n}$ term in there. I would greatly appreciate any help in this exercise.

Thanks

Solving $u_{\epsilon \eta} = \frac{ u_\epsilon – u_eta}{4 (\epsilon – \eta) } .$

I’m trying to solve the following PDE

$ $ y^2 u_{xx} – u_{yy} = 0.$ $

I’ve found its canonical form as $ $ u_{\epsilon \eta} = \frac{ u_\epsilon – u_eta}{4 (\epsilon – \eta) } .$ $

However, I’m having trouble in solving this PDE. I’ve tried solving with mathematica, and that gave me

$ $ u = \frac{ x + y^3}{ 3} ,$ $ but, I need to know how to obtain such a result from the canonical form of the given PDE.