[PDF] [PDF] Formal Languages Automata and Computation DFAs to Regular





Previous PDF Next PDF



Lecture 4: Regular Expressions and Finite Automata

Kleene's regular expressions also appeared as Type-3 languages in ls lecture*.pdf. – rm -rf *. ... Can we construct a DFA/NFA for a regular expression?



Regular expression to dfa examples pdf

The set of regular languages ??is closed under the following: Complement Intersection Union Concatenation Star (Kleene Closure) L1 = {W a {0.1} *



Formal Languages Automata and Computation DFAs to Regular

A language is regular if and only if some regular expression describes DFA-TO-GNFA-RE CONVERSION EXAMPLE ... Lectures/2005-slides/lec09.pdf.



Regular Expressions and Regular Languages

We will give an algorithm which converts a given regular expression to a NFA. • We have already discussed how to convert a NFA to a DFA using subset 



Regular Languages

If a language is regular then it can be described by a regular expression. ? Two steps. ? DFA into GNFA (generalized nondeterministic finite automaton). ? 



q1 q2 q3 a b b a a b

Definition: A language is regular if it is recognized by some DFA. CS 341: Chapter 1. 1-12. Examples of Deterministic Finite Automata.



Regular Expressions Regular Expressions

The two are actually equivalent so RE = NFA = DFA. – We can define an algebra for regular expressions RE Examples. • L(001) = {001}.



From Regular Expression to NFA to DFA

(NFA) from RE and Subset construction Algorithm can be applied to convert the NFA into a. Deterministic Finite Automaton (DFA).



Homework 3 Solutions

steps of the algorithm to obtain an equivalent DFA. (b) Prove that L has a regular expression where L is the set of strings satisfying all.



6.045J Lecture 4: NFAs and regular expressions

Regular expressions denote FA-recognizable languages Theorem: If M is an NFA then L(M) is DFA-recognizable. • Proof: ... Example: NFA ? DFA.



[PDF] Regular Expressions and Converting an RE to a DFAJP - JFLAP

The following algorithm facilitates the conversion from a RE for language L to a DFA for language L by first converting the RE to a nondeterministic finite



[PDF] Regular Expressions • DFA • NFA Examples

DFA can be always be constructed from NFA (state expansion) with potential exponential increase in state space S F E general machine S F ?



[PDF] Lecture 4: Regular Expressions and Finite Automata - Cse iitb

– Let C be a regular expression where each Li is concretized to some letters a1a2 am – Then every string w in L(E) can be written as w1w2 wk where wi 



[PDF] Formal Languages Automata and Computation DFAs to Regular

A language is regular if and only if some regular expression describes In fact all standard DFA transitions are generalized



[PDF] Equivalence of DFA and Regular Expressions - CUHK CSE

In general how do we convert a regular expression to an NFA? A regular expression over ? is an expression formed by the following rules ? The symbols ? and 



[PDF] Equivalence of DFA and Regular Expressions - CUHK CSE

In general how do we convert a regular expression to an NFA? A regular expression over ? is an expression formed by the following rules • The symbols 0 and ? 



[PDF] CS 301 - Lecture 3 NFA DFA Equivalence Regular Expressions

Equivalence of NFA and DFA – Regular Expressions – Equivalence to Regular Languages Equivalence of Machines Machine is equivalent to machine if 1



[PDF] Regular Expressions and Regular Languages

We will give an algorithm which converts a given regular expression to a NFA • We have already discussed how to convert a NFA to a DFA using subset 



[PDF] From Regular Expression to NFA to DFA

To construct a NFA from this use Thompson's construction This method constructs a regular expression from its components using ?-transitions The ?



[PDF] q1 q2 q3 a b b a a b - New Jersey Institute of Technology

Regular Expressions • Nonregular Languages CS 341: Chapter 1 1-3 Introduction Definition: A deterministic finite automaton (DFA) is a 5-tuple

:

FORMALLANGUAGES, AUTOMATA AND

COMPUTATION

DFAS TOREGULAREXPRESSIONS

DFA MINIMIZATION- CLOSUREPROPERTIES

Carnegie Mellon University in Qatar

(CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 1 / 39 SUMMARYRegular Expression (RE) define regular sets RE)NFA)DFA(CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 2 / 39

EQUIVALENCE OFRES TOFINITEAUTOMATATHEOREMA language is regular if and only if some regular expression describes

it.LEMMA- THEonly ifPARTIf a language is regular then it is described by a regular expression PROOFIDEAGeneralized transitions:label tr ansitionswith regular e xpressions

Generalized NFA

s (GNFA) Iteratively eliminate states of the GNFA one by one, until only two states and a single generalized transition is left. (CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 3 / 39 GENERALIZEDTRANSITIONSDFAs have single symbols as transition labels If you are in statepand the next input symbol matchesa, go to stateqNow consider If you are in statepanda prefix of the remaining input

matches the regular expressionab[bcthen go to stateq(CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 4 / 39

GENERALIZEDTRANSITIONS ANDNFAA generalized transition is a transition whose label is a regular expressionA Generalized NFA is an NFA with generalized transitions.In fact, all standard DFA transitions are generalized transitions with regular expressions of a single symbol! (CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 5 / 39

GENERALIZEDTRANSITIONSConsider the 2-state DFA

0

1takes the DFA from stateq0toq1(0[101)takes the machine fromq1back toq1So?=01(0[101)represents all strings that take the

DFA from stateq0toq1(CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 6 / 39 GENERALIZEDNFASTake any DFA and transform it into a GNFA with only two states: one start and one accept with one generalized transition then we can "read" the regular expression from the label of the generalized transition (as in the example above) (CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 7 / 39

DFATOGNFAWe will add two new states to a DFA:

A ne wstar tstate with an -transition to the original start state, but with no tr ansitionsfrom an yother state Ane wfinal state with an -transition from all the original final states, but with no tr ansitionsto an yother state The previous start and final states are no longer! (CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 8 / 39 REDUCING AGNFAWe eliminate all states of the GNFAone-b y-one leaving only the start state and the final state.When the GNFA is fully converted,the label of the only generalized transition is the regular expression f orthe language accepted b ythe original DFA. (CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 9 / 39 ELIMINATINGSTATESSuppose we want to eliminate stateqk, andqi andqjare two of the remaining states (i=jis possible).How can we modify the transition label between q iandqjto reflect the fact thatqkwill no longer

be there?There are two paths betweenqiandqjDirect path with regular expressionrijPath viaqkwith the regular expressionrikrkkrkj(CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 10 / 39

ELIMINATINGSTATESThere are two

paths betweenqiandqjDirect path with regular expression r ijPath viaqkwith the regular expression r ikrkkrkjAfter removingqk, the new label would be r

0ij=rij[rikrkkrkj#

(CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 11 / 39

DFA-TO-GNFA-RE CONVERSIONEXAMPLEDFA for binary

numbers divisible by 3Initial GNFA (CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 12 / 39 DFA-TO-GNFA-RE CONVERSIONEXAMPLELet"s eliminateq2q i=q1;qj=q1;qk=q2(CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 13 / 39

DFA-TO-GNFA-RE CONVERSIONEXAMPLELet"s eliminateq1(CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 14 / 39

DFA-TO-GNFA-RE CONVERSIONEXAMPLELet"s eliminateq0So the regular expression we are looking for is (1(010)1[0)(CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 15 / 39 THESTORYSOFAR(CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 16 / 39 THESTORYSOFAR(CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 17 / 39 DFA MINIMIZATIONEvery DFA defines a unique language

But in general, there may be many DFAs for a

given language.These DFAs accept the same language. (CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 18 / 39 DFA MINIMIZATIONIn practice, we are interested in the DFA with the minimal number of statesUse less memory

Use less hardware (flip-flops)

(CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 19 / 39 INDISGUISHABLESTATESTwo statespandqof a DFA are calledindistinguishableif f orall !2, (p;!)2F,(q;!)2F, and (p;!)62F,(q;!)62F,Basically, these two states behave the same for

all possible strings!Hence, a statepisdistinguishab lefrom state qIf there is at least one string!such that either(p;!)2F

or(q;!)2Fand the other isnot (CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 20 / 39

INDISTINGUISHABILITYIndistinguishable states behave the same for all possible strings!So why have indistinguishable states? All but one can be eliminated!Indistinguishability is anequiv alencerelation

Reflexive

: Each state is indistinguishable from itself

Symmetric

: Ifpis indistinguishable fromq, thenqis indistinguishable frompTransitive: Ifpis indistinguishable fromq, andqis

indistinguishable fromr, thenpis indistinguishable fromr.(CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 21 / 39

INDISTINGUISHABILITY ANDPARTITIONSIndistinguishability is anequiv alencerelation

Reflexive

:Each state is indistinguishable from itself

Symmetric

: Ifpis indistinguishable fromq, thenqis indistinguishable frompTransitive: Ifpis indistinguishable fromq, andqis indistinguishable fromr, thenpis indistinguishable fromr.An equivalence relation on a setQinduces a partitioning=f1;2;;kgsuch thatFor alliandj,i\j= ,S ii=Q(CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 22 / 39 IDENTIFYINGDISTINGUISHABLESTATESBasis: Any nonaccepting state is distinguishable from any accepting state (!=).Induction: Statespandqare distinguishable if there is some input symbolasuch that(p;a)is distinguishable from(q;a).All other pairs of states areindistinguishab le, and can be merged appropriately (CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 23 / 39 IDENTIFYINGDISTINGUISHABLESTATESpis distinguishable fromqandrby basisBothqandrgo top with 0, so no string beginning with 0 will distinguish themStarting in eitherqand r, an input of 1 takes us to either, so they are indistinguishable. (CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 24 / 39

IDENTIFYINGDISTINGUISHABLESTATES

The Procedure MARK1Remove all inaccessible states

2Consider all pairs of states(p;q)ifp2Fandq62Forp62Fandq2F,mar k(p;q)as

distinguishable3Repeat the following until no previously unmarked

pairs are marked8p;q2Qand8a2, find(p;a) =p0and(q;a) =q0,if(p0;q0)is marked distinguishable then mark(p;q)

distinguishable. (CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 25 / 39

MINIMIZATIONEXAMPLEq

1andq2are equivalentq

3andq4are equivalentq

5andq6are equivalentq

1xxxxx

q

2Xxxxx

q 3xxx q 4Xxx q 5x q 6X xq 0q 1q 2q 3q 4q

5(CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 26 / 39

THEMINIMIZEDDFAq

1andq2are equivalentq

3andq4are equivalentq

5andq6are equivalentq

1xxxxx

q

2Xxxxx

q 3xxx q 4Xxx q 5x q 6X xq 0q 1q 2q 3q 4q

5(CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 27 / 39

IS THE MINIMIZEDDFAREALLY MINIMAL?LetMbe the DFA found by the previous procedure (with statesP=fp0;p1;:::;pmg)Suppose there is an equivalent DFAM1with1 but with fewer states (Q=fq0;q1:::;qngn0is) such that1(q0;!k) =1(q0;!l)(Pigeonhole principle-see later )Sincepkandplare distinguishable, there must be some stringxsuch that (p0;!kx) =(pk;x)is a final state and (p0;!lx) =(pl;x)is NOT a final state, or vice versa.

So!kxis accepted and!lxis not (or vice versa)(CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 29 / 39

IS THE MINIMIZEDDFAREALLY MINIMAL?But

1(q0;!kx) =1(1(q0;!k);x)

=1(1(q0;!l);x) =1(q0;!lx)SoM1either accepts both!kxand!lxor

rejects both. SoM1andMcan not be equivalent.SoM1can not exist.(CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 30 / 39

MORE ONDFA MINIMIZATIONDFA minimization is not covered in the textbook. See http://www.cs.uiuc.edu/class/sp06/cs273/ Lectures/2005-slides/lec09.pdfIntroduction to Automata Theory, Languages and Computation, by Hopcroft, Motwani and Ullman, Addison

Wesley, 3

rdedition, Section 4.4 for more formal details. (CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 31 / 39

CLOSUREPROPERTIES OFREGULAR

LANGUAGESRegular languages are closed under

Union

Intersection

Difference

Concatenation

Star Closure

Complementation

Reversal

operations (CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 32 / 39

HOMOMORPHISMSupposeandare alphabets, the function

h: !is called ahomomor phismIt is a substitution in whicha single symbol a2 is replaced by a stringx2, that is.h(a) =xExtend to strings:h(!) =h(a1):::;h(an)where

!2andai2Extend to languagesh(L) =fh(!)j!2Lgh(L)is called thehomomor phicimage of L.(CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 33 / 39

HOMOMORPHISMEXAMPLELet =fa;bgand =fa;b;cgh(a) =abandh(b) =bbch(aba) =abbbcabTHEOREMLet h be a homomorphism. If L is regular then h(L)is

also regular.PROOFObvious: Modify the DFA transitions (CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 34 / 39

DECISIONPROPERTIES OFREGULAR

LANGUAGESTHEOREMGiven a standard representation (DFA, NFA, RE) of any regular language L onand any!in, there

exists an algorithm to determine if!is in L or not.PROOF.Represent the language with a DFA and test if!is

accepted or not (CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 35 / 39

DECISIONPROPERTIES OFREGULAR

LANGUAGESTHEOREMThere exist algorithms for determining whether a regular language in standard representation is empty or not.PROOF.Represent the language with a DFA. If there is a path from the start state to some final state, the language is not empty. (CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 36 / 39

DECISIONPROPERTIES OFREGULAR

LANGUAGESTHEOREMThere exist algorithms for determining whether a regular language in standard representation is finite or infinite.PROOF.Find all states that form a cycle. If any of these are on path from the

start state to a final state, then the language is infinite.PROOF.If DFA withnstates accepts some string of length betweennand

2n1 then it accepts an infinite set of strings.(needs Pumping

Lemma)(CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 37 / 39

DECISIONPROPERTIES OFREGULAR

LANGUAGESTHEOREMGiven standard representations of two regular languages L

1and L2, there exists an algorithm to

determine if L

1=L2.PROOF.ComputeL3= (L1L2)[(L2L1)which has to be

regular. IfL3= thenL1=L2.(CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 38 / 39

MOREDECISIONPROBLEMSTo decide ifL1L2,check ifL1L2= To decide if2L,check ifq02FTo decide ifLcontains!such that!=!RLetMbe the DFA forL. ConstructMR.ConstructM\MRusing the cross-product constructionCheck ifL(M\MR)6= .(CARNEGIEMELLONUNIVERSITY INQATAR)SLIDES FOR15-453 LECTURE5SPRING2011 39 / 39

quotesdbs_dbs14.pdfusesText_20
[PDF] regular expression to dfa questions

[PDF] regular expression to grammar converter

[PDF] regular expression to nfa in c

[PDF] regular graph

[PDF] regular language closed under concatenation

[PDF] regular language to regular grammar

[PDF] regular octagonal prism volume

[PDF] regular overtime

[PDF] regular solution

[PDF] regular solution model

[PDF] regular solution model interaction parameter

[PDF] regular solution theory equation

[PDF] regular verb in pdf

[PDF] regular verbs list pdf

[PDF] regularization and optimization