Lab 0: Grammars and Formal Languages¶
Theory assignment¶
These assignments are optional for those who need to revise their theory knowledge of regular expressions and formal languages. The lab is intended to make you practice using the basic concepts used in descriptions of formal languages.
Given the alphabet
and the strings x=
2
, y=13
, z=323
:What are the strings xz, zyx, z2, z7; and what are their lengths?
What are A1, A2, A0?
Describe A* and A+.
Given:
<exp> ::= <term> | <exp> + <term> | <exp> - <term> <term> ::= <factor> | <term> * <factor> | <term> / <factor> <factor> ::= ( <exp> ) | <ident> <ident> ::= A | B | C ... | Z
A*B-C A*(B-C) A/B/C -A*B
Find derivations and draw a parse tree for the statements in Listing 3.
State the handle in statement form
<term> * <factor> + B/C
State a canonical derivation of one of the statements in Listing 3.
Why is
A * <exp> * D
not in statement form?What are
,
, and
in this grammar?
Describe
and
. State some string in
which is not in
.
Using the grammar in Listing 2, draw the parse tree for the statement:
A - <term> * B + ( <term> )
Use this to explain why there is no canonical derivation of the statement.
Construct a context-free grammar for even integers which may not begin with zeros (this also applies to a single zero).
provide a regular expression for strings consisting of binary numbers separated by the operators
or
. Example:
10+1001-01 111001
Draw the respective state diagram, too.
Given the alphabet
:
Construct a context-free grammar for words of one syllable (i.e. words containing exactly one vowel).
Construct a context-free grammar for multi-syllable words.
Given the alphabet
:
Write regular a expression which describes all strings starting with a sequence of zero or several
a
‘s followed by an arbitrary number ofb
‘s andc
‘s mixed together. The strings finish with another sequence ofa
‘s. (Example:aaabbcbca
,bbca
,aa
).Can the expression
be described using a regular expression? If so, write down the regular expression. If not, motivate why.
Describe the languages (sets) that the following grammars generate:
<S>
is the start symbol.<S> ::= <A> <A> <A> ::= 1 <A> 0 | 10
<S> ::= 1 <S> 0 | <B> <B> ::= 0 <B> 1 | ε
<S> ::= 1 <A> | <B> 0 <A> ::= 1 <A> | <C> <B> ::= <B> 0 | <C> <C> ::= 1 <C> 0 | ε