2.Defining Languages - Slide Example Solutions

================================================================================

Regular Languages (type 3)


Production Rules:

S -> aS | aT
T -> bU | U
U -> ε | cU

produce each of the following:

--------------------------------------------------------------------------------

aabc:

   S
=> aS
=> aaT
=> aabU
=> aabcU
=> aabc

--------------------------------------------------------------------------------

ac:

   S
=> aT
=> aU
=> acU
=> ac

--------------------------------------------------------------------------------

a:

   S
=> aT
=> aU
=> a

================================================================================

Example Grammar (type 2)

Program →  Stmts
Stmts   →  Stmt | Stmt ; Stmts
Stmt    →  Var = Expr  |  print Expr
Var     →  a | b | c | d
Expr    →  Expr  + Term | Expr – Term  |  Term
Term    →  Var | Const
Const   → Digit | Digit Const
Digit   →  0 | 1 | 2 | … | 9 

--------------------------------------------------------------------------------

example:  c=1

   Program
=> Stmts
=> Stmt
=> Var = Expr
=> c = Expr
=> c = Term
=> c = Const
=> c = Digit
=> c = 1

--------------------------------------------------------------------------------

example: a=3;b=a+1;print b

   Program
=> Stmts
=> Stmt; Stmts
=> Var = Expr; Stmts
=> a = Expr; Stmts
=> a = Term; Stmts
=> a = Const; Stmts
=> a = 3; Stmts
=> a = 3; Stmt; Stmts
=> a = 3; Var = Expr; Stmts
=> a = 3; b = Expr; Stmts
=> a = 3; b = Expr + Term; Stmts
=> a = 3; b = Term + Term; Stmts
=> a = 3; b = Var + Term; Stmts
=> a = 3; b = a + Term; Stmts
=> a = 3; b = a + Const; Stmts
=> a = 3; b = a + Digit; Stmts
=> a = 3; b = a + 1; Stmts
=> a = 3; b = a + 1; Stmt
=> a = 3; b = a + 1; print Expr
=> a = 3; b = a + 1; print Term
=> a = 3; b = a + 1; print Var
=> a = 3; b = a + 1; print b

================================================================================

Practice Problems (Production Rules)

--------------------------------------------------------------------------------

recognize the language described by {a^nb^n|n≥1}
(n a's, followed by n b's, where n≥1).

S -> aSb | ab

Another alternative:

S -> aSb | T
T -> ab

--------------------------------------------------------------------------------

Create production rules that recognize lists of single digits, e,g, [2,4,6,8]

Let's clarify that we want to accept the empty list as well.


S -> [] | [D] | [D,I]
I -> D | D,I
D -> 0|1|2|3|4|5|6|7|8|9

================================================================================

Practice Problems - Ambiguity

Consider a language with if-statements and if-else statements. Create a string showing the ambiguity.

S ⟶ if S then S | if S then S else S | true | false | print



idea: we want an else that could attach to either of two if's, which are nested.

the string:     if true then if true then print else print

showing that it's ambiguous: two leftmost derivations of the same string, but using different rules. (they describe different parse trees)

   S
=> if S then S else S
=> if true then S else S
=> if true then if S then S else S
=> if true then if true then S else S
=> if true then if true then print else S
=> if true then if true then print else print


   S
=> if S then S
=> if true then S
=> if true then if S then S else S
=> if true then if true then S else S
=> if true then if true then print else S
=> if true then if true then print else print

--------------------------------------------------------------------------------

Fix the grammar above so that is not ambiguous.

idea: we need a bit of syntax that clearly ends an if-stmt.

S -> if S then S endif | if S then S else S endif | true | false | print

our previous string's two versions would now  be:

if true then if true then print endif else print endif
if true then if true then print       else print endif endif 

================================================================================

================================================================================

================================================================================

================================================================================

================================================================================

================================================================================