Scribd
Upload
4 views11 pages

Understanding Regular Expressions Basics

This document discusses regular expressions and their use in describing formal languages. It defines what constitutes a regular expression and provides examples of regular expressions over the alphabet {0,1}. The document also introduces generalized non-deterministic finite automata and describes how to convert a GNFA to a regular expression.

Uploaded by

shivagat
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views11 pages

Understanding Regular Expressions Basics

This document discusses regular expressions and their use in describing formal languages. It defines what constitutes a regular expression and provides examples of regular expressions over the alphabet {0,1}. The document also introduces generalized non-deterministic finite automata and describes how to convert a GNFA to a regular expression.

Uploaded by

shivagat
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

REGULAR EXPRESSIONS

REGULAR EXPRESSIONS We say that R is a regular expression if R is 1. a for some a , 2. , 3. , 4. (R1 R2 ), where R1 and R2 are regular expressions, 5. (R1 R2 ), where R1 and R2 are regular expressions,
6. (R1 ), where R1 is a regular expressions.

Let = {0, 1}, {w|w has exactly two 1 s}

Let = {0, 1}, {w|w has at least two 1 s}

Let = {0, 1}, {w|whas even number of 1 s}

A language is regular i some regular expression describes it

If a language is described by a regular expression, then it is regular

A generalized non-deterministic nite automata is a 5-tuple M = (Q, , , q0 , qf ).

Converting a GNFA to a regular expression

10

Convert the following FA to a regular expression

11

You might also like