CSCE 121 Grammar

From Notes
Jump to navigation Jump to search


Grammars are chains of logic rules that can be used to interpret data:

LHS → RHS

Way to apply rules:

  1. start with a particular Left Hand Side
  2. continually replace using rules until you're stuck

Applications

Mostly used in artificial intelligence

  • Expert Systems (medicine)
  • Logic programming
  • Interpret natural languages
  • Interpret programming languages
  • Other data: music, dance, RNA structure, 2D graphics

Example

Describe all strings of parentheses that are balanced:

( )( ) OK
( ( ) ) OK
( ( ) ) ) NOT OK
( ( ) ( ) ) OK
( ) ) ( NOT OK

Rules

  1. S → ( S )
  2. S → S S
  3. S → empty string

Going top-down picking rules at randomgenerates a string of parentheses that will be balanced

Retrieved from "https://notes.komputerwiz.net/w/index.php?title=CSCE_121_Grammar&oldid=139"