CH3

Question 1

what is the role of Regular expressions?

Answer 1

important notations for specifying lexeme patterns

Question 2

a finite set of symbols

Answer 2

alphabet

Question 3

what are symbols?

Answer 3

letter, digit , or punctuation mark .

Question 4

What is ASCII?

Answer 4

an alphabet used in SW

Question 5

A finite sequence of symbols drawn from an alphabet

Answer 5

String(Word)

Question 6

number of occurrences of symbol in s

Answer 6

length of a string

Question 7

how is a length of a string denoted

Answer 7

|s|

Question 8

what is a language

Answer 8

a countable set of strings generated from a fixed alphabet

Question 9

what is a formal language

Answer 9

all possible strings that can be generated from an alphabet.

Question 10

In lexical analysis, the most important operations on languages are

Answer 10

Union
Concatenation
Closure(Kleene star, and Kleene +)

Question 11

How do you represent a java identifier in the form of a regular expression?

Answer 11

L(L or D)*
in which letters include an underscore

Question 12

It is used for describing all the languages that can be built from these operators (Union, concatenation, and Kleene closure), applied to the symbols of some alphabet.

Answer 12

Regular Expressions.

Question 13

are used to describe tokens of a programming language

Answer 13

Regular expressions

Question 14

What is a regular expression built from?

Answer 14

smaller regular expressions

Question 15

True/False
All regular expressions denote the same language.

Answer 15

False.
Each regular expression denotes a language.

Question 16

True/False
Regular expressions are widely used to specify patterns.

Answer 16

True

Question 17

What is a regular set?

Answer 17

A language that is denoted by a regular expression

Question 18

What are the rules of Regular expressions built from?

Answer 18

Union
Concatenation
Closure(Kleene star, and Kleene +)

Question 19

Formally, the set of regular expressions can be defined by the following recursive rules:

Answer 19

1. epsilon is a regular expression
2. every symbol in the Language is a Regular expression
3. if r1 and r2 are regular expressions then so are r1|r2, r1 r2 , r1*
4. Nothing else is a Regular expression

Question 20

How can we remove parentheses in Regular Expressions?

Answer 20

By using precedence rules

Question 21

What are the precedence rules?

Answer 21

1. closure(*)
2. concatenation
3. union

Question 22

Describe the role of regular definitions.

Answer 22

Some regular expressions may be quite complex, so regular definitions are used to denote those complex regular expressions as symbols

Question 23

What is a recognizer?

Answer 23

It is also called a program for a language, and it is also called a finite automata. It takes a string ‘x’ and tells whether this string belongs to the language or not. If it belongs, it answers ‘yes’ and if it doesn’t belong, it answers ‘no’. It is also a machine that has a finite number of states and transitions.

Question 24

What are the types of finite automaton?

Answer 24

DFA and NFA

Question 25

NFA and DFA can be used as a ....

Answer 25

Lexical analyzer

Question 26

Both NFA and DFA recognize ...

Answer 26

Regular Sets

Question 27

which of the types of finite automaton is used as a lexical analyzer?

Answer 27

Both of them. but DFA is considered to be widely used as a lexical analyzer

Question 28

State the differences between DFA and NFA

Answer 28

*DFA* - can be converted to efficient programs - faster recognizer, but it may take more space - widely used as a lexical analyzer *NFA* - not closer to real machines - can’t be converted to efficient programs - slower, but it may take less space

Question 29

What are the algorithms responsible to converting RE to DFA

Answer 29

Definition of RE i done first for tokens then : 1. RE->NFA->DFA 2. RE->DFA

Question 30

NFA is a mathematical model that consists of :

Answer 30

1. input alphabet/symbols 2. a finite set of states denoted by circles 3 a transition function for each state and symbol that belongs to the alphabet(including the epsilon, the specifies the next state)(denoted by an arrow). 4. start state s0 that has an arrow pointing to it denoting that it is the start state 5. final/acceptance set of states denoted by double circles.

Question 31

Epsilon-transitions are allowed in ..

Answer 31

NFA

Question 32

what do we mean by Epsilon-transitions?

Answer 32

that we can move from state to state without consuming any symbol

Question 33

When does the NFA accept a string?

Answer 33

when there is a path from the starting state and moving through states by following valid transitions based on the input symbols until reaching to the final acceptance state with the correct string.

Question 34

A Deterministic Finite Automaton (DFA) is a special form of a NFA that obey a number of additional restrictions.State them

Answer 34

1. no epsilon transitions 2. no identically labeled transitions of the same state 3. we never have a choice of several next states 4. the state and next input symbol uniquely identifies the transition.

Question 35

"no identically labeled transitions of the same state" this is a DFA rule. what does it mean?

Answer 35

it means we never have a choice of several next states

Question 36

what uniquely determines the transition (or lack of same)?

Answer 36

the state and the next input symbol

Question 37

What is the reason of the name of the automata DFA

Answer 37

because each state and the next input symbol uniquely identifies a transition

Question 38

How is the transition function defined in DFA?

Answer 38

move(s,c) a state s reached by a state s from any transition of symbol c.

Question 39

If there was a transition function move(s,c), and there wasn't any transition. How is this case defined?

Answer 39

It is defined as that there is no epsilon transition

Question 40

Describe Thomson's construction in two words

Answer 40

simple and systematic

Question 41

How many final states does Thomson's construction guarantee that the resulting NFA will have?

Answer 41

One resulting Final State

Question 42

State the steps for Thomson's Construction

Answer 42

1. from each subexpression construct a NFA fragment 2. combine these fragments

Question 43

True/False a fragment can be a complete

Answer 43

False. it can be a complete NFA construction by adding the necessary components to make a complete NFA.

Question 44

What does an NFA fragment consist of?

Answer 44

NFA fragment = a number of states + transitions between these states

Question 45

A fragment has 2 incomplete transitions. State and define them.

Answer 45

1. Incoming Half Transition : points into the fragment without consuming any input symbol 2. Outgoing Half Transition : points out of the fragment, it is labeled by an epsilon or an alphabet symbol

Question 46

which of the incomplete transitions of a fragment allows the movement to another fragment or state?

Answer 46

Outgoing Half Transition

Question 47

..... serves to identify the starting state of the completed NFA.

Answer 47

Incoming Half Transition

Question 48

When an NFA fragment has been constructed for the whole regular expression, the construction is completed by connecting the ..... to an accepting state

Answer 48

Outgoing Half Transiton

Question 49

we allow a NFA to have several accepting states, a NFA constructed using this method will have only one.which method is meant here?

Answer 49

Thomson’s Construction

Question 50

we allow a NFA to have several accepting states, a NFA constructed using this method will have only one. when is the final state added?

Answer 50

at the end of the construction