Regular Expressions (Discrete Mathematics: Formal Languages and Automata)

Опубликовано: 07 Январь 2021
на канале: Frank Stajano Explains

4,204

I am a Professor in the Computer Science department at the University of Cambridge. Through this channel I welcome anyone in the world to attend my lectures. This is the first video in a series on Formal Languages and Automata that forms the last part of the Discrete Mathematics course for first year computer scientists.

Today's video introduces regular expressions as a way to define a formal language: the language is the set of strings that the regular expression recognises.

This video, and indeed this series of lectures, is not about learning how to write, optimize and debug regular expressions. We are instead concerned with exploring the expressive power of regular expressions---what languages they are capable of recognizing and what are their limitations.

We open with a distinction between concrete and abstract syntax. The abstract syntax for a regular expression is a tree structure, whereas the concrete syntax is a linearized sequence of characters from a set that includes (a) the alphabet over which the strings to be recognized are defined, plus (b) six special metacharacters, not present in that alphabet, used to define the regular expression.

Many thanks to those of you who are giving thumbs up to these videos and subscribing to the channel. Your support is greatly appreciated and it causes Youtube to offer this material to more viewers who might like it.

Course web page:
https://www.cl.cam.ac.uk/teaching/cur...

Course handout:
https://www.cl.cam.ac.uk/teaching/202...

My home page:
http://frank.stajano.com