[LAC]Introduction to languages

Introduction to languages

Overview

In this year, i enrolled a module called Language and Computation which will cover automata theory, languages and computation.
In the very first view, we need to define what are languages and the related terms.
Reference: Introduction to Automata Theory, Languages, and Computation.
A language is a (possibly infinite) set of words.
A word is a finite sequence (or string) of symbols.
ε denotes the empty word, the sequence of zero symbols.
A symbol is anything, but it has to come from an alphabet Σ which is a finite set
A common (and important) instance is Σ = {0, 1}.
ε, the empty word, is never a symbol of an alphabet.

alphabet

so what is the difference between “alphabet” and “symbol”?
On the reference book 1.5.1, it says, “an alphabet is a finite, non-empty set of symbols”
Conventionally, we use the symbol Σ for an alphabet. Common alphabets include:
1. Σ = {0, 1}, the binary alphabet
2. Σ = {a, b, …, z}, the set of all lower-case letters
3. The set of all ASCII characters, or the set of all printable ASCII characters

power of an alphabet

We define Σ^k to be the set of strings of length k, each of whose symbols is in Σ.
enter image description here
Note that there is a slight confusion between Σ and Σ1. The former is an alphabet, its members 0 and 1 are symbols. The latter is a set of strings; its members are the strings 0 and 1, each of which is of length 1.

All words over an alphabet

enter image description here
The set of all words(strings) over an alphabet Σ is conventionally denoted Σ. For instance, {0, 1} = {ε, 0, 1, 00, 01, 10, 11, 000, …}
Is Σ* always non-empty?
Yes because alphabet is nonempty set of symbols! and even empty word belongs to Σ*
note that if we say xw, it is the concatenation of strings which is x concatenated with w.
enter image description here

Exam questions

Is the following statement correct?
The empty word ε belongs to all languages
No, it is not correct
Let’s review the relationship between alphabet Σ, language and Σ*(a set of words)
A set of strings all of which are chosen from some Σ*, where Σ is a particular alphabet, is called language.
So empty word is in Σ*, and it can be language
But it doesn’t belongs to all languages, like the picture above, {a}, {b} both doesn’t have empty word.

评论

发表评论

此博客中的热门博文

[MLE] W2 Multivariate linear regression

图片
Multivariate linear regression What we have talked about in week 1 is linear regression with single feature. For example, in the house pricing predicting problem, we only use the size of house (x) to predict the price (y) . But what if there are other features like age, bedroom numbers and so on? Linear regression with multiple variables is also known as “multivariate linear regression” According to the graph above, we now have new representation symbols: n = number of features m = number of training examples \(x^{(i)}\) = \(i^{th}\) training example \(x^{(i)}_j\) = feature j in \(i^{th}\) training example 1416 is \(x_{1}^{(2)}\) in this case, m is 47 for example, n is 4. Hypothesis function The multivariable form of the hypothesis function accommodating these multiple features is as follows: if we make \(x_0\) to 1, the \(h_{\theta}(x)\) will be \(\theta^Tx\), which is \(\theta\) transpose matrix multiply by x, where \(\theta\) is a vector of 1 by(n+1) dimension an
阅读全文

[MLE] W1 Introduction

图片
Before get started The blog is based on the machine learning course on Coursera, taught by Andrew Ng . From today, i will begin my study trip on Machine learning, which will be labelled as MLE. This course will last 11 weeks and today is week 1. The application of machine learning is everywhere: Database mining Applications can’t program by hand Self-customizing program Understanding human learning(brain, real AI) Introduction What is Machine Learning Two definitions of machine learning are offered: Arthur Samuel described it as: “the field of study that gives computers the ability to learn without being explicitly programmed.” This is an older, informal definition. Tom Mitchell provides a more modern definition: “A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.” If we raise a example of what is machine learning: If
阅读全文

[AIM] MetaHeuristics

图片
Day2 Outline Metaheuristics -definition Single point based search method(simple stochastic local search) Iterated local search Scheduling Tabu Search Metaheuristic what is a metaheuristic? A metaheuristic is a high-level problem independent algorithmic framework that provides a set of guidelines or strategies to develop heuristic optimization algorithms. what is the difference between heuristic and metaheuristic? Heuristic : Heuristics are problem-dependent techniques. As such, they usually are adapted to the problem at hand and they try to take full advantage of the particularities of this problem. However, because they are often too greedy, they usually get trapped in a local optimum and thus fail, in general, to obtain the global optimum solution. Metaheuristic : Meta-heuristics, on the other hand, are problem-independent techniques . As such, they do not take advantage of any specificity of the problem and, therefore, can be used as black boxes . In general, t
阅读全文