MODULES 1-3 Flashcards
Midterm Summative Assessment Reviewer
COURSE: RECAP
Course code
S-CSPC327
COURSE: RECAP
Course title
Automata Theory and Formal Languages
COURSE: RECAP
Full name of the professor
Ms. Jennylinde R. Manaois
COURSE: RECAP
The course allows the students to analyze formal models in computer science, including _, _, _, _, and _.
regular expressions,
finite automata,
context-free grammars,
pushdown automata,
Turing machines
COURSE: RECAP
At the end of the course, the students are expected to develop a simple _ that will check the syntax of a certain string if it is a valid string or not in a particular language.
compiler
COURSE: RECAP
Module 1: Introduction to Computer Theory
Module 2: Regular Expression
Module 3: Finite Automata
Noted
MODULE 1: QUESTION
It is the study of abstract computing devices or “machines.”
Automata Theory
MODULE 1: QUESTION
It is a study of mathematical model of a computer which can determine whether a particular string is in a language.
Automata Theory
MODULE 1: QUESTION
It is a concept that describes how machine mimic human behavior.
Automata Theory
MODULE 1: QUESTION
It is an abstract model of a digital computer.
Automata
MODULE 1: INFO
Every automaton includes some essential features.
* It has mechanism for reading input.
* It is also assumed to operate in a discrete time frame.
Noted
MODULE 1: QUESTION
Every automaton has a mechanism for reading _.
input
MODULE 1: QUESTION
An automaton is assumed to operate in a _ time frame.
discrete
MODULE 1: QUESTION
It provides a model way in which computers can parse some language.
Automata
MODULE 1: QUESTION
A mathematical model for a finite state machine.
Automata
MODULE 1: QUESTION
It is a machine that given an input, jumps through a series of states according to a transition function that tells the automaton which state to go next given a current state and a current symbol.
Finite State Machine
MODULE 1: INFO
Brief History of Automata
* Alan Turing in the 1930’s introduced his abstract model – Turing Machines – that had all the capabilities of today’s computers.
* In the 1940’s and 1950’s, simpler kinds of machines, called finite automata were studied by Rabin, Scott and others.
* In the late 1950’s, Noam Chomsky introduced formal grammars representing languages accepted by abstract automata.
Noted
MODULE 1: QUESTION
These are the most powerful abstract machines.
Turing Machines
MODULE 1: INFO
Why study Automata?
Finite Automata are useful model for many important kinds of hardware and software.
Noted
MODULE 1: INFO
List of Some Applications of the Concept of Finite Automata
* Software for designing and checking the behavior of digital circuits. (ex. on/off switch)
* The “lexical analyzer” of a typical compiler.
* Software for scanning large bodies of text, such as collections of Web pages, to find occurrences of words, phrases, or other patterns.
* Software for verifying systems of all types that have a finite number of distinct states.
Noted
MODULE 1: INFO
There are important notations that are not automaton-like, but play an important role in the study of automata and their application.
1. Grammars
2. Regular Expression
Noted
MODULE 1: RECAP
Automaton-like formal models in Computer Science
Finite Automata, Pushdown Automata, and the Turing machines
MODULE 1: RECAP
Non-automaton-like formal models in Computer Science
Grammars and Regular Expression
MODULE 1: QUESTION
These are useful models when designing software that processes data with a recursive structure.
Grammars
The best known example is a parser – the component of a compiler that deals with recursively nested features of the typical programming languages.
MODULE 1: QUESTION
The component of a compiler that deals with recursively nested features of the typical programming languages.
parser
The best known example of Grammars.
MODULE 1: QUESTION
This denotes the structure of data, especially text strings.
Regular Expression
MODULE 1: INFO
Introduction to Computer Theory Summary
* Core mathematics of CS (not changed in over 30 years)
* Many applications, especially in design f compilers and programming languages
* To be able to recognize incomputable and intractable problems
* In order to be computer scientist, not simply a computer programmer
Noted
MODULE 1: QUESTION
_ is any finite set of symbols.
Alphabet (∑)
Common alphabets include:
1. ∑ = { 0,1 } - binary alphabet
2. ∑ = { a,b, …., z } - the set of all lowercase letters
3. The set of all ASCII characters, or the set of all printable ASCII characters.
MODULE 1: RECAP
A symbol that denotes alphabets
∑
MODULE 1: QUESTION
_ is a finite sequence of symbols from some alphabet.
String ( Word )
e.g. aba, 01001
MODULE 1: QUESTION
The empty string with zero occurrences
of symbols is denoted by _.
Λ
MODULE 1: QUESTION
It is the number of positions for symbols in the string.
String length
MODULE 1: QUESTION
String length is denoted by _
|string|
e.g. |0110| = 4, |Λ| = 0
MODULE 1: INFO
Powers of an alphabet ∑ is defined as the set of strings of length k and denoted by ∑^k.
k - length of string
Noted
MODULE 1: QUESTION
The set of all strings over an alphabet ∑ is denoted by _
∑*
Alphabet symbol with Kleene Closure
∑* = ∑0 ∑1 ∑2 ….
MODULE 1: QUESTION
The set of nonempty strings over ∑ is denoted by _.
∑+
Alphabet symbol with Positive Closure
MODULE 1: INFO
String Concatenation
if x and y are strings then xy denotes the concatenation of x and y.
Noted
MODULE 1: QUESTION
It is the set of strings ( words ) chosen from some alphabet
Language
The language may be infinite, but there is some finite set of symbols of which all its strings are composed.
MODULE 1: QUESTION
This denotes the empty language over any alphabet.
A symbol resembling a stop sign, but with a longer horizontal line extending from right to left across its center.
MODULE 1: QUESTION
It is the symbol of the language consisting of only the empty string.
{ Λ }
An upside down V inside the curly braces.
MODULE 1: INFO
Note that { Λ } ≠ (empty language)
The former has one string, the latter has no strings.
Noted
MODULE 1: INFO
Some examples of Languages
1. The set of all binary strings consisting of some number of 0’s followed by an equal number of 1’s
2. The language of all strings consisting of n 0’s followed by n 1’s, for some n ≥ 0
3. The set of compilable C programs
4. English words
Noted
MODULE 1: INFO
“Set-former” as a Way to Define Languages:
{w|something about w }
1. {w | w consists of an equal number of 0’s and 1’s} (*)
2. {w | w is syntactically correct C program}
3. {w | w is a set of words built according to the rules
of English grammar}
4. {0^n1^n | n ≥ 0}
Noted
MODULE 2: QUESTION
It is a sequence of pattern that defines a string.
Regular Expression
MODULE 2: QUESTION
These are used to match character combinations in strings.
Regular Expression
MODULE 2: QUESTION
String searching algorithm used this pattern to find the operations on a string.
Regular Expression
MODULE 2: QUESTION
It is the most effective way to represent any language.
Regular Expression
MODULE 2: INFO
The symbols that appear in regular expressions are the letters of the alphabet (Σ), the symbol for the null string (Λ), parentheses (), the star operator (*), and the plus (or) sign (+).
Noted
MODULE 2: INFO
The set of regular expressions is defined by the following rules:
Rule 1: Every letter of Σ can be made into a regular expression by writing it in boldface; Λ is a regular expression.
Rule 2: If r1, and r2 are regular expressions, then so are:
1. (rl)
2. r1r2
3. r 1 + r 2
4. rl*
Rule 3: Nothing else is a regular expression.
Noted
MODULE 2: INFO
The various operations on regular language are:
Union: If L and M are two regular languages then their union L U M is also a union.
1. L U M = {s | s is in L or s is in M}
Intersection: If L and M are two regular languages then their intersection is also an intersection.
1. L ⋂ M = {st | s is in L and t is in M}
Kleene closure: If L is a regular language then its Kleene closure L1* will also be a regular language.
1. L* = Zero or more occurrence of language L
Noted
MODULE 2: INFO
Some RE Examples:
Regular Expression | Regular Set
(0+10*) | L= { 0, 1, 10, 100, 1000, 10000, … }
(0* 1 0*) | L= {1, 01, 10, 010, 0010, …}
(0+ε)(1+ Λ) | L= {Λ0, 1, 01}
(a+b)* | Set of strings of a’s and b’s of any length including the null string. So L= { ε, a, b, aa, ab, bb, ba, aaa, …}
(a+b)*abb | Set of strings of a’s and b’s ending with the string abb. So L = {abb, aabb, babb, aaabb, ababb, …}
(11)* | Set consisting of even number of 1’s including empty string
Noted
MODULE 3: QUESTION
It is the simplest abstract machine to recognize patterns with input taken from the given alphabet.
Finite Automata (FA)
The job of an FA is to accept or reject an input depending on whether the pattern defined by the FA occurs in the input.
MODULE 3: QUESTION
Its job is to accept or reject an input depending on whether the pattern defined by this occurs in the input.
Finite Automata (FA)
MODULE 3: INFO
A finite automaton is a collection of three things:
1. A finite set of states, one of which is designated as the initial state, called the start state, and some of which are designated as final states.
2. An alphabet Σ of possible input letters, from which are formed strings, that are to be read one letter at a time.
3. A finite set of transitions that tell for each state and for each letter of the input alphabet which state to go to next.
Noted
MODULE 3: QUESTION
What are the two types of Finite Automaton?
- Deterministic Finite Automaton (DFA)
- Non-deterministic Finite Automaton (NDFA/NFA)
MODULE 3: INFO
DETERMINISTIC FINITE AUTOMATA
- In a DFA, for a particular input character, the machine goes to one state only. A transition function is defined on every state for every input symbol. Also in DFA null (Λ) move is not allowed, i.e., DFA cannot change state without any input character.
- For example, below DFA with Σ = {a, b} accepts all strings starting with either a or b.
NOTE:
* There can be many possible DFAs for a pattern.
* A DFA with minimum number of states is generally preferred.
See presentation for examples
Noted
MODULE 3: INFO
NON-DETERMINISTIC FINITE AUTOMATA (NFA)
NFA is similar to DFA except following additional features:
- Null (Λ) move is allowed i.e., it can move forward without reading symbols.
- Ability to transmit to any number of states for a particular input. However, these above features don’t add any power to NFA. If we compare both in terms of power, both are equivalent.
See presentation for examples
Noted
