Assignment $$ Week $2$

No Author Given

Department of Computer Science

California State University, Los Angeles

I$)$ Give a formal definition with any notations for each of the following: Alpha$-$

bet, String, Language, Concatenation of strings, Reverse of a string, Substring,

Length of a string, Star$-$Closure of an alphabet, Positive Closure of an alphabet,

Sentence of a language.

II$)$ For a language L$,$ describe the Complementation, and Star$-$Closure.

III$)$ Describe the relationship of Language, Grammar and Automata $($over a

given alphabet$).$

IV$)$ Write derivations for four strings of various lengths and describe what is

the language generated, L$($G$)$ by the following grammar G$.$

V $=\{$S$,$ A$,$ B$\},$ T $=\{$a$,$ b$\}$

P $=$ S $->$ A$,$ S $->$ B$,$ B $->$ bB$,$ A $->$ aA$,$ A $->\backslash$lambda $,$ B $->\backslash$lambda $,$

S is the start nonterminal.

V$)$ Write derivations for four strings of various lengths and describe what is

the language generated, L$($G$)$ by the following grammar

S $->$ aSaa$|$B$,$ B $->$ bB$|\backslash$lambda

VI$)$ Write derivations for four strings of various lengths and describe what is

the language generated, L$($G$)$ by the following grammar

S $->$ aSaa$|$B$,$ B $->$ bB

VII$)$ Describe the operation of Automaton as an Accepter.

VIII$)$ Let X $=\{$a$,$ b$\}$

L$1=\{$a$,$ ab$,$ abb$\}$

L$2=\{\backslash$lambda $,$ b$,$ bb$\}$

Describe all the following languages as a set of strings.

$1)$ L$3=$ L$1\backslash$cap L$2$

$2)$ L$1$L$3$

$3)$ L$3$L$1$

$4)$ L$1$L$2$

$5)$ L$1$

$6)$ LR

$1$

$7)$ LR

$2$

$8)$ P$$

$9)$ L$2$

$10)$ L$0$

$1$

$11)$ L$1$