Automata Course - Revision history

Adamcolton: /* Regular Expression */

2013-11-12T20:10:06Z

Regular Expression

← Older revision		Revision as of 20:10, 12 November 2013
Line 71:		Line 71:
	Union is simple. Concatenation produces a sort of cross product. The Kleene star is just the star - it represents any string in L.		Union is simple. Concatenation produces a sort of cross product. The Kleene star is just the star - it represents any string in L.

	Ø + x = x		Ø + R = R

			εR = Rε = R

			ØR = RØ = Ø

	I missed something here, I may need to go through this again.		I missed something here, I may need to go through this again.

2013-11-12T20:05:29Z

Regular Expression

← Older revision		Revision as of 20:05, 12 November 2013
Line 70:		Line 70:

	Union is simple. Concatenation produces a sort of cross product. The Kleene star is just the star - it represents any string in L.		Union is simple. Concatenation produces a sort of cross product. The Kleene star is just the star - it represents any string in L.

			Ø + x = x

			I missed something here, I may need to go through this again.

	==== Regular Expressions in the Real World ====		==== Regular Expressions in the Real World ====
	==== Decision Algorithms for Regular Languages ====		==== Decision Algorithms for Regular Languages ====
	==== Closure properties of Regular Languages ====		==== Closure properties of Regular Languages ====

2013-11-12T19:46:21Z

Regular Expression

← Older revision		Revision as of 19:46, 12 November 2013
Line 64:		Line 64:
	=== Week 2 ===		=== Week 2 ===
	==== Regular Expression ====		==== Regular Expression ====
			RE's use three operations
			* Union (+)
			* Concatenation (no operator)
			* Kleene star (*)

			Union is simple. Concatenation produces a sort of cross product. The Kleene star is just the star - it represents any string in L.

	==== Regular Expressions in the Real World ====		==== Regular Expressions in the Real World ====
	==== Decision Algorithms for Regular Languages ====		==== Decision Algorithms for Regular Languages ====
	==== Closure properties of Regular Languages ====		==== Closure properties of Regular Languages ====

2013-11-12T18:48:13Z

Video Lectures

← Older revision		Revision as of 18:48, 12 November 2013
Line 61:		Line 61:

	There's a lot in here, but it all boils down to DFAs where individual states represent sets of states in the NFA or ε-NFA.		There's a lot in here, but it all boils down to DFAs where individual states represent sets of states in the NFA or ε-NFA.

			=== Week 2 ===
			==== Regular Expression ====
			==== Regular Expressions in the Real World ====
			==== Decision Algorithms for Regular Languages ====
			==== Closure properties of Regular Languages ====

2013-11-12T15:51:06Z

Nondeterministic Finite Automata

← Older revision		Revision as of 15:51, 12 November 2013
Line 60:		Line 60:
	For any NFA there is a DFA that accepts the same language. The proof is the subset construction.		For any NFA there is a DFA that accepts the same language. The proof is the subset construction.

	There's a lot in here, but it all boils down to DFAs where individual states represent sets of states in the NFA or &~~Epsilon~~;-NFA.		There's a lot in here, but it all boils down to DFAs where individual states represent sets of states in the NFA or ε-NFA.

2013-11-12T15:50:19Z

Nondeterministic Finite Automata

← Older revision		Revision as of 15:50, 12 November 2013
Line 58:		Line 58:
	δ takes a set of states that it could be in and produces a set of states it could be in given those states.		δ takes a set of states that it could be in and produces a set of states it could be in given those states.

	For any NFA there is a DFA that accepts the same language. The proof is ~~teh~~ subset construction.		For any NFA there is a DFA that accepts the same language. The proof is the subset construction.

			There's a lot in here, but it all boils down to DFAs where individual states represent sets of states in the NFA or Ε-NFA.

2013-11-11T22:03:05Z

Deterministic Finite Automata

← Older revision		Revision as of 22:03, 11 November 2013
Line 51:		Line 51:
	In proofs, an implication statement that is true because the "if" portion is false is said to be true vacuously.		In proofs, an implication statement that is true because the "if" portion is false is said to be true vacuously.

	A ~~languageL~~ is regular if it is the language accepted by some DFA, and the DFA accepts only the strings in L.		A language L is regular if it is the language accepted by some DFA, and the DFA accepts only the strings in L.

			==== Nondeterministic Finite Automata ====
			Has the ability to be in several states at once.

			δ takes a set of states that it could be in and produces a set of states it could be in given those states.

			For any NFA there is a DFA that accepts the same language. The proof is teh subset construction.

2013-11-11T20:26:24Z

Deterministic Finite Automata

← Older revision		Revision as of 20:26, 11 November 2013
Line 46:		Line 46:
	* A start state, q<sub>0</sub>		* A start state, q<sub>0</sub>
	* A set of final (or accepting) states, F where F &sube; Q.		* A set of final (or accepting) states, F where F &sube; Q.

			The transition function takes a state and an input symbol and returns a state, the state that the DFA will proceed to.

			In proofs, an implication statement that is true because the "if" portion is false is said to be true vacuously.

			A languageL is regular if it is the language accepted by some DFA, and the DFA accepts only the strings in L.

2013-11-11T19:52:58Z

Deterministic Finite Automata

← Older revision		Revision as of 19:52, 11 November 2013
Line 30:		Line 30:

	==== Deterministic Finite Automata ====		==== Deterministic Finite Automata ====
			An alphabet is any finite set of symbols, such as letters and is represented as Σ

			A string over an alphabet Σ is a list where each element is a member of Σ

			Σ* = set of all strings over alphabet Σ

			Ε stands for the empty string.

			A language is a subset of Σ* for some alphabet Σ.

			Deterministic Finite Automata
			* A finite set of states, Q
			* An input alphabet, Σ
			* A transition function δ
			* A start state, q<sub>0</sub>
			* A set of final (or accepting) states, F where F &sube; Q.

2013-11-11T19:43:49Z

Informal Introduction to Finite Automata

← Older revision		Revision as of 19:43, 11 November 2013
Line 28:		Line 28:
	* important component of comilers		* important component of comilers
	* describes simple patterns of events		* describes simple patterns of events

			==== Deterministic Finite Automata ====