Print Options

Card layout:

← Back to notecard set|Easy Notecards home page

Instructions for Side by Side Printing
  1. Print the notecards
  2. Fold each page in half along the solid vertical line
  3. Cut out the notecards by cutting along each horizontal dotted line
  4. Optional: Glue, tape or staple the ends of each notecard together
  1. Verify Front of pages is selected for Viewing and print the front of the notecards
  2. Select Back of pages for Viewing and print the back of the notecards
    NOTE: Since the back of the pages are printed in reverse order (last page is printed first), keep the pages in the same order as they were after Step 1. Also, be sure to feed the pages in the same direction as you did in Step 1.
  3. Cut out the notecards by cutting along each horizontal and vertical dotted line
Print these notecards...Print as a list

24 notecards = 6 pages (4 cards per page)

Viewing:

COT 6410 Computational Complexity Midterm

front 1

Deterministic Finite Automata notation

back 1

A = {Q, Σ, δ, q_0, F}
Q - set of states

Σ - alphabet

δ - transition function

q_0 - start state

F - finale state

front 2

δ(current state, character) = state you would have transitioned to

back 2

δ(current state, character) = state you would have transitioned to

front 3

How do you reverse a language represented as a DFA

back 3

- Change start state to final state

- Change finale state(s) to start state(s)

- Reverse the transitions

(optional) - create a new state that λ transitions to all the start states

front 4

How to tell if something is a Regular Language?

back 4

A DFA or NFA can recognize it

front 5

Difference between DFA and NFA

back 5

DFA due to its deterministic nature must have a transition out of every state for every character in the alphabet, and NO λ transitions. Also note every DFA is technically also an NFA

NFA doesn't have to have a transition for every alphabet character and can have λ transitions. Also note every NFA has an equivalent DFA

front 6

some primitive notation

back 6

Φ = {}

λ = {λ}

a means where 'a' is in Σ denotes {a}

front 7

Closure properties for R and S

back 7

R · S

R + S

R*

front 8

convert this to a reg ex using (R_ij)^k method

back 8

in 1-16 notes

front 9

convert this to a reg ex using state ripping

back 9

in 1-16 notes

front 10

convert this to a reg ex using Arden's

back 10

in 1-21 notes

front 11

Show the relation between the following family of languages. Regular, Deterministic Context-Free, Context-
Free, and Context-Sensitive

back 11

front 12

Show the relation between models of computation

back 12

front 13

True or False: Every NFA does not have an equivalent DFA

back 13

true, you can turn an nfa into usually a nasty much larger dfa with stuff like trap states.

front 14

Does an algorithm exist for determining if a grammar is considered ambiguous?

back 14

no, ambiguity is undecidable

front 15

Whenever a new problem is created, what is it considered inherently?

back 15

solvable and unsolved

front 16

solved is temporal or inherited

back 16

temporal

front 17

unsolvable/undecidable is temporal or inherited

back 17

temporal

front 18

unsolved is temporal or inherited

back 18

inherited

front 19

if we solve that new problem it moves from

solvable and unsolved

to?

back 19

solvable and solved

front 20

if we find that new problem is unsolvable it moves from

solvable and unsolved

to?

back 20

unsolved and solved

front 21

Can the CYK parsing algorithm take any type of grammar as input?

back 21

CYK operates only on context-free grammars given in Chomsky normal form

front 22

Find the minimal equivalent DFA using the method that was shown in class.

back 22

1-23 slides

front 23

True or False: The reversal operation is closed under regular languages.

back 23

true earlier card says how

front 24

Express the following FSA as a regular expression using Arden's Theorem..

back 24

1-21 slides