Theoretical Aspects of Lexical Analysis - Revision history

Root: Redirected page to ist:Theoretical Aspects of Lexical Analysis

2018-12-05T22:06:40Z

Redirected page to ist:Theoretical Aspects of Lexical Analysis

Root: /* Exercises from exams and tests */

2018-07-06T07:57:53Z

Exercises from exams and tests

← Older revision		Revision as of 07:57, 6 July 2018
Line 439:		Line 439:
	* [[Theoretical Aspects of Lexical Analysis/Exercise 23\|Exercise 23]]: <nowiki>G = { a\|b, b\|c, a*c }</nowiki>, input string = abbcac, Teste 2018/04/07		* [[Theoretical Aspects of Lexical Analysis/Exercise 23\|Exercise 23]]: <nowiki>G = { a\|b, b\|c, a*c }</nowiki>, input string = abbcac, Teste 2018/04/07
	* [[Theoretical Aspects of Lexical Analysis/Exercise 24\|Exercise 24]]: <nowiki>G = { a\|b, bc, a\|c* }</nowiki>, input string = abbcac, Teste 2018/04/07		* [[Theoretical Aspects of Lexical Analysis/Exercise 24\|Exercise 24]]: <nowiki>G = { a\|b, bc, a\|c* }</nowiki>, input string = abbcac, Teste 2018/04/07
			* [[Theoretical Aspects of Lexical Analysis/Exercise 25\|Exercise 25]]: <nowiki>G = { a\|b, bc, (a\|c)* }</nowiki>, input string = abbcac, Teste 2018/07/05

	[[category:Compiladores]]		[[category:Compiladores]]
	[[category:Ensino]]		[[category:Ensino]]
	[[en:Theoretical Aspects of Lexical Analysis]]		[[en:Theoretical Aspects of Lexical Analysis]]

Root: /* Exercises */

2018-04-19T14:54:17Z

Exercises

← Older revision		Revision as of 14:54, 19 April 2018
Line 403:		Line 403:
	== Exercises ==		== Exercises ==

			=== Acceptors ===
	For each regular expression, compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. In each case, compute the minimal deterministic finite automaton (DFA).<br/>The alphabet is '''Σ = { a, b }''' in all cases.		For each regular expression, compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. In each case, compute the minimal deterministic finite automaton (DFA).<br/>The alphabet is '''Σ = { a, b }''' in all cases.

Line 409:		Line 410:
	* [[Theoretical Aspects of Lexical Analysis/Exercise 3\|Exercise 3]]: <nowiki>((ε\|a)b)*</nowiki>		* [[Theoretical Aspects of Lexical Analysis/Exercise 3\|Exercise 3]]: <nowiki>((ε\|a)b)*</nowiki>
	* [[Theoretical Aspects of Lexical Analysis/Exercise 4\|Exercise 4]]: <nowiki>(a\|b)abb(a\|b)</nowiki>		* [[Theoretical Aspects of Lexical Analysis/Exercise 4\|Exercise 4]]: <nowiki>(a\|b)abb(a\|b)</nowiki>

			=== Multi-token recognition: lexical analyzers ===

	For each ordered sequence, compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. In each case, compute the minimal deterministic finite automaton (DFA).<br/>The alphabet is Σ = { a, b } in all cases. Indicate the number of processing steps for each input string.		For each ordered sequence, compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. In each case, compute the minimal deterministic finite automaton (DFA).<br/>The alphabet is Σ = { a, b } in all cases. Indicate the number of processing steps for each input string.
Line 414:		Line 417:
	* [[Theoretical Aspects of Lexical Analysis/Exercise 5\|Exercise 5]]: <nowiki>G = { ab, ab*, a\|b }</nowiki>, input string = abaabb		* [[Theoretical Aspects of Lexical Analysis/Exercise 5\|Exercise 5]]: <nowiki>G = { ab, ab*, a\|b }</nowiki>, input string = abaabb
	* [[Theoretical Aspects of Lexical Analysis/Exercise 6\|Exercise 6]]: <nowiki>G = { aa, aaaa, a\|b }</nowiki>, input string = aaabaaaaa		* [[Theoretical Aspects of Lexical Analysis/Exercise 6\|Exercise 6]]: <nowiki>G = { aa, aaaa, a\|b }</nowiki>, input string = aaabaaaaa

			=== Exercises from exams and tests ===

	The following appeared in written tests (same task as before):		The following appeared in written tests (same task as before):
Line 433:		Line 438:
	* [[Theoretical Aspects of Lexical Analysis/Exercise 22\|Exercise 22]]: <nowiki>G = { a\|b, bc, a*\|c }</nowiki>, input string = abbcac, Teste 2017/04/01		* [[Theoretical Aspects of Lexical Analysis/Exercise 22\|Exercise 22]]: <nowiki>G = { a\|b, bc, a*\|c }</nowiki>, input string = abbcac, Teste 2017/04/01
	* [[Theoretical Aspects of Lexical Analysis/Exercise 23\|Exercise 23]]: <nowiki>G = { a\|b, b\|c, a*c }</nowiki>, input string = abbcac, Teste 2018/04/07		* [[Theoretical Aspects of Lexical Analysis/Exercise 23\|Exercise 23]]: <nowiki>G = { a\|b, b\|c, a*c }</nowiki>, input string = abbcac, Teste 2018/04/07
			* [[Theoretical Aspects of Lexical Analysis/Exercise 24\|Exercise 24]]: <nowiki>G = { a\|b, bc, a\|c* }</nowiki>, input string = abbcac, Teste 2018/04/07

	[[category:Compiladores]]		[[category:Compiladores]]
	[[category:Ensino]]		[[category:Ensino]]
	[[en:Theoretical Aspects of Lexical Analysis]]		[[en:Theoretical Aspects of Lexical Analysis]]

Root: /* Exercises */

2018-04-17T16:46:49Z

Exercises

← Older revision		Revision as of 16:46, 17 April 2018
Line 432:		Line 432:
	* [[Theoretical Aspects of Lexical Analysis/Exercise 21\|Exercise 21]]: <nowiki>G = { ab, b\|c, a*\|c }</nowiki>, input string = abbcac, Teste 2017/04/01		* [[Theoretical Aspects of Lexical Analysis/Exercise 21\|Exercise 21]]: <nowiki>G = { ab, b\|c, a*\|c }</nowiki>, input string = abbcac, Teste 2017/04/01
	* [[Theoretical Aspects of Lexical Analysis/Exercise 22\|Exercise 22]]: <nowiki>G = { a\|b, bc, a*\|c }</nowiki>, input string = abbcac, Teste 2017/04/01		* [[Theoretical Aspects of Lexical Analysis/Exercise 22\|Exercise 22]]: <nowiki>G = { a\|b, bc, a*\|c }</nowiki>, input string = abbcac, Teste 2017/04/01
			* [[Theoretical Aspects of Lexical Analysis/Exercise 23\|Exercise 23]]: <nowiki>G = { a\|b, b\|c, a*c }</nowiki>, input string = abbcac, Teste 2018/04/07

	[[category:Compiladores]]		[[category:Compiladores]]
	[[category:Ensino]]		[[category:Ensino]]
	[[en:Theoretical Aspects of Lexical Analysis]]		[[en:Theoretical Aspects of Lexical Analysis]]

Root: /* Exercises */

2017-04-01T17:31:47Z

Exercises

← Older revision		Revision as of 17:31, 1 April 2017
Line 430:		Line 430:
	* [[Theoretical Aspects of Lexical Analysis/Exercise 19\|Exercise 19]]: <nowiki>G = { a\|b, b\|c, c*\|a }</nowiki>, input string = abbcac		* [[Theoretical Aspects of Lexical Analysis/Exercise 19\|Exercise 19]]: <nowiki>G = { a\|b, b\|c, c*\|a }</nowiki>, input string = abbcac
	* [[Theoretical Aspects of Lexical Analysis/Exercise 20\|Exercise 20]]: <nowiki>G = { a\|b, b\|c, a*\|c }</nowiki>, input string = abbcac, Teste 2016/04/08		* [[Theoretical Aspects of Lexical Analysis/Exercise 20\|Exercise 20]]: <nowiki>G = { a\|b, b\|c, a*\|c }</nowiki>, input string = abbcac, Teste 2016/04/08
			* [[Theoretical Aspects of Lexical Analysis/Exercise 21\|Exercise 21]]: <nowiki>G = { ab, b\|c, a*\|c }</nowiki>, input string = abbcac, Teste 2017/04/01
			* [[Theoretical Aspects of Lexical Analysis/Exercise 22\|Exercise 22]]: <nowiki>G = { a\|b, bc, a*\|c }</nowiki>, input string = abbcac, Teste 2017/04/01

	[[category:Compiladores]]		[[category:Compiladores]]
	[[category:Ensino]]		[[category:Ensino]]
	[[en:Theoretical Aspects of Lexical Analysis]]		[[en:Theoretical Aspects of Lexical Analysis]]

Root: /* Regular Expressions */

2017-02-28T16:35:19Z

Regular Expressions

← Older revision		Revision as of 16:35, 28 February 2017
Line 24:		Line 24:

	Other:		Other:
	* Begining: '''^''' ('''^abc''' means '''abc''' at the beginning of the string")		* Begining: '''^''' ('''^abc''' means "'''abc''' at the beginning of the string")
	* End: '''$''' ('''abc$''' means "'''abc''' at the end of the string")		* End: '''$''' ('''abc$''' means "'''abc''' at the end of the string")
	* Character class negation: '''[^ ..... ]''' (e.g., "'''[^a-z]''' means any character except a lower-case letter between '''a''' and '''z'''")		* Character class negation: '''[^ ..... ]''' (e.g., '''[^a-z]''' means "any character except a lower-case letter between '''a''' and '''z'''")

	== Recognizing/Matching Regular Expressions: Thompson's Algorithm ==		== Recognizing/Matching Regular Expressions: Thompson's Algorithm ==

Root: /* Exercises */

2016-04-08T18:13:08Z

Exercises

← Older revision		Revision as of 18:13, 8 April 2016
Line 429:		Line 429:
	* [[Theoretical Aspects of Lexical Analysis/Exercise 18\|Exercise 18]]: <nowiki>G = { ab, (a\|c), bc* }</nowiki>, input string = abbcac		* [[Theoretical Aspects of Lexical Analysis/Exercise 18\|Exercise 18]]: <nowiki>G = { ab, (a\|c), bc* }</nowiki>, input string = abbcac
	* [[Theoretical Aspects of Lexical Analysis/Exercise 19\|Exercise 19]]: <nowiki>G = { a\|b, b\|c, c*\|a }</nowiki>, input string = abbcac		* [[Theoretical Aspects of Lexical Analysis/Exercise 19\|Exercise 19]]: <nowiki>G = { a\|b, b\|c, c*\|a }</nowiki>, input string = abbcac
			* [[Theoretical Aspects of Lexical Analysis/Exercise 20\|Exercise 20]]: <nowiki>G = { a\|b, b\|c, a*\|c }</nowiki>, input string = abbcac, Teste 2016/04/08

	[[category:Compiladores]]		[[category:Compiladores]]
	[[category:Ensino]]		[[category:Ensino]]
	[[en:Theoretical Aspects of Lexical Analysis]]		[[en:Theoretical Aspects of Lexical Analysis]]

Root: /* DFA Minimization */

2016-03-01T08:21:24Z

DFA Minimization

← Older revision		Revision as of 08:21, 1 March 2016
Line 218:		Line 218:
	* Final states, F = {2, 3, 4, 5}; and non-final states, NF = {1};		* Final states, F = {2, 3, 4, 5}; and non-final states, NF = {1};
	* Considering ''a'' and F: 2, 4, and 5 present similar behavior (all have transitions ending in states in the same set, i.e., 4); 3 presents a different behavior (i.e., no ''a'' transition). Thus, we get two new sets: {2, 4, 5} and {3};		* Considering ''a'' and F: 2, 4, and 5 present similar behavior (all have transitions ending in states in the same set, i.e., 4); 3 presents a different behavior (i.e., no ''a'' transition). Thus, we get two new sets: {2, 4, 5} and {3};
	* Considering ''b'' and {2, 4, 5} we reach a conclusion ~~similar to the one for ''a'', i.e.,~~ all states ~~have transitions to state 5 and cannot, thus, be distinguished~~ from each other;		* Each new partition must now be reassessed;
			* Considering both ''a'' and ''b'' and {2, 4, 5}, we reach the conclusion that all states are indistinguishable from each other;
	* Since {2, 4, 5} has no ''c'' transitions, it remains as is. Since all other sets are singular, the minimization process stops.		* Since {2, 4, 5} has no ''c'' transitions, it remains as is. Since all other sets are singular, the minimization process stops.

Root: /* Exercises */

2015-04-14T09:31:28Z

Exercises

← Older revision		Revision as of 09:31, 14 April 2015
Line 427:		Line 427:
	* [[Theoretical Aspects of Lexical Analysis/Exercise 17\|Exercise 17]]: <nowiki>G = { a, ba, a*\|b }</nowiki>, input string = aababb		* [[Theoretical Aspects of Lexical Analysis/Exercise 17\|Exercise 17]]: <nowiki>G = { a, ba, a*\|b }</nowiki>, input string = aababb
	* [[Theoretical Aspects of Lexical Analysis/Exercise 18\|Exercise 18]]: <nowiki>G = { ab, (a\|c), bc* }</nowiki>, input string = abbcac		* [[Theoretical Aspects of Lexical Analysis/Exercise 18\|Exercise 18]]: <nowiki>G = { ab, (a\|c), bc* }</nowiki>, input string = abbcac
			* [[Theoretical Aspects of Lexical Analysis/Exercise 19\|Exercise 19]]: <nowiki>G = { a\|b, b\|c, c*\|a }</nowiki>, input string = abbcac

	[[category:Compiladores]]		[[category:Compiladores]]
	[[category:Ensino]]		[[category:Ensino]]
	[[en:Theoretical Aspects of Lexical Analysis]]		[[en:Theoretical Aspects of Lexical Analysis]]

Root at 14:35, 6 April 2015

2015-04-06T14:35:52Z

← Older revision		Revision as of 14:35, 6 April 2015
Line 428:		Line 428:
	* [[Theoretical Aspects of Lexical Analysis/Exercise 18\|Exercise 18]]: <nowiki>G = { ab, (a\|c), bc* }</nowiki>, input string = abbcac		* [[Theoretical Aspects of Lexical Analysis/Exercise 18\|Exercise 18]]: <nowiki>G = { ab, (a\|c), bc* }</nowiki>, input string = abbcac

	[[category:~~Teaching~~]]		[[category:Compiladores]]
	[[category:~~Compilers~~]]		[[category:Ensino]]
	[[en:Theoretical Aspects of Lexical Analysis]]		[[en:Theoretical Aspects of Lexical Analysis]]