Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

#A2 Computing > FSM, Regular expressions, BNF > Flashcards

FSM, Regular expressions, BNF Flashcards

1
Q

What is a moore machine?

A

Outputs at each state (including when it starts)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

what is a mealy machine?

A

The outputs are from the transitions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Why are FSM’s useful?

A

model many kinds of task eg a language, controller, protocols, spellcheck.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Define FSM?

A

Consiits of a set of inputs symbolsa, and produces a set of output symbols.

Finite number of stats with tranition rules

can have an output or not.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is a halting state in a fsm

A

A state that has no outgoing transiitons

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a non-deterministic FSM?

A

An fsm that may have several possible next states for each pair of state and input symbol.

(eg an input of 1 has 2 transitions, and which it does is decided by weather the fsm can get to the acceptor)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Deterministic FSM

A

has one next state for each input

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is a FSA?

A

Finite state automaton

an fsm which has no output until the end where it outputs yes or no.

(yes producing states are the accepting states)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a regular expression?

A

a notation for defining all the valid strings of a formal language or for defining a search pattern

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What does | mean in regular equarssions?

A

or (has the lowest priority)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What does * mean in regular equarssions?

A

0 or more

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What does ? mean in regular equarssions?

A

0 or 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What does + mean in regular equarssions?

A

1 or more

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What does ( ) mean in regular equarssions?

A

grouping

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

what does [] mean in regular expressions?

A

Whats inside the brackets is the class, and shows all allowable characters eg [ae] is a or e.

[a-z]-lowercase

[a-zA-Z]any letter

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

what does [^] mean in regular expressions?

A

anything but eg [^t] is anything but t

17
Q

what does \d mean in regular expressions?

A

any numeric character

18
Q

what does \w mean in regular expressions?

A

any alpha numeric character

19
Q

what does \s mean in regular expressions?

A

space

20
Q

what does \W (captital) mean in regular expressions?

A

its not \w or [^\w]

21
Q

what does . mean in regular expressions?

A

it matches any character

22
Q

applications of regular expressions

A
  • searcing for files
  • searching for words in a block of text
  • searching for virus signatures
  • filtering text
23
Q

What is a turning machine?

A

An FSM that controls one + tapes that are infinite and can move in both directions. Can execute any algothrithm

24
Q

What does a TM do at each step?

A
  • Changes state
  • Changes symbol on tape
  • Moves the tape 1 step (or doesnt move)
25
Q

What problems cana TM solve?

A

any computable problem will have a Tm that will halt with the correct output for all inputs

26
Q

Transition lables for a TM

A

input,Input | Outputs Direction

eg 1,0 | # <–

27
Q

Whats a halting state in a Tm?

A

Double circle.

It stops the machine

28
Q

Transition rule format for TM

A

𝛿( CurrentState, On Tape ) = (NextState,output,movetape)

eg

𝛿(S0,{0,1})=(S1, ,->)

29
Q

What is a transition table

A

A table that shows each state, and where each input will take the machine and what output it gives

30
Q

what is a universal Turing machine?

A

A turing machine that can execute other turning machines, by first inputting the transition rules then the data.

(Interpriter reads rules of the TM its simulating)

(program is fed into it like data)

31
Q

What is BNF?

A

backus-Naur form

a notation for expressing the rules for constructing valid stings in a regular langeage

(defines the syntax)

32
Q

BNF format

A

<name> : : = Definition</name>

33
Q

How would recursion work in BNF?

(1 or more of somehting happeneing)

A

<list> ::=<thing> | <thing><list></list></thing></thing></list>

34
Q

What is a parse tree?

A

A pictorial representation showing how a valid thing conforms to the rules.

(a break down of the input and what groups each section will belone to, with the smallest group being at the bottom of the tree, and then the input is there.

35
Q

What is a Syntax diagram

A

ALternative way to define syntax (visual BNF)

36
Q

Syntax diagram and its symbols

A

In circle is the words that are needed

In rectangles are the other defined things.

#A2 Computing (8 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions