QUESTION BANK SOLUTION Unit 1 Introduction to Finite Automata
4. Define DFA NFA & Language? (5m)( Jun-Jul 10). Deterministic finite automaton (DFA)—also known as deterministic
Finite Automata
of L and the choice of automaton. ○ The entire rest of the quarter will be dedicated to answering these questions.
QUESTION BANK Unit 1 Introduction to Finite Automata
Draw a DFA to accept string of 0's and 1's ending with the string 011. (4m)( Dec-Jan 10) (Jun-Jul 12). 7. Write DFA to accept strings of 0's 1's & 2's
Theory of Computation - (Finite Automata)
24.01.2021 г. Solution. The DFA accepts the string bbab. The computation is: 1. Start in state q0. 2. Read b follow transition from q0 to q1.
Formal Models of Question‐Answering Machine
27.04.2021 г. Abstract. The article describes two models of question-answering dialogue machine: (1) model based on the idea of Mealy finite automata ...
Solutions to the exercises on Finite Automata
Find a deterministic finite-state automaton that recognizes the same language as the nondeter- ministic finite-state automaton in Exercise 19. Solution. Let
Automata Spring 2022
https://www.cs.utep.edu/vladik/cs3350.22/finalSolutions.pdf
Finite Automata Pattern Recognition and Perceptrons
possible responses of the automaton in question. Let the vector which is the binary representation of the integer N be denoted by r
CS 352 – Compiling and Programming Systems Mid-term
The total points is 100 (ie your grade will be the percentage of your answers that are correct). (Finite automata; 35%). (a) (10%) Draw an NFA for the ...
Finite Automata and Their Decision Problems#
cause the automaton to give a “yes” answer. Finally we shall treat in this section the question of deciding whether two automata define the same set of tapes.
QUESTION BANK SOLUTION Unit 1 Introduction to Finite Automata
4. Define DFA NFA & Language? (5m)( Jun-Jul 10). Deterministic finite automaton (DFA)—also known as deterministic
QUESTION BANK SOLUTION Unit 1 Introduction to Finite Automata
4. Define DFA NFA & Language? (5m)( Jun-Jul 10). Deterministic finite automaton (DFA)—also known as deterministic
2 MARKS QUESTIONS WITH ANSWERS & 16 MARK QUESTIONS
NFA can be used in theory of computation because they are more flexible and easier to use than DFA. Deterministic Finite Automaton is a FA in which there is
Regular Languages and Finite Automata
1 REGULAR EXPRESSIONS. The answer to question (a) on Slide 9 is 'yes'. Algorithms for deciding such pattern- matching questions make use of finite automata.
Finite Automata
dedicated to answering these questions. Page 15. To Summarize. ? An automaton is an idealized mathematical
Nondeterministic Finite Automata
In a nondeterministic finite automaton (NFA) for each state there can be zero
FORMAL LANGUAGES AND AUTOMATA THEORY
Finite automaton is very useful in recognizing difficult problems i.e. sometimes it general solution exists for the specified problem
Finite Automata and Their Decision Problems#
Then the machine is turned on and the question is typed in; after an “end of question” button is pressed a light indicates a “yes” or. “no” answer. Other good
DD2372 Automata and Languages – Problems from previous exams
Give a deterministic finite automaton over the alphabet {a Solution: Here is a standard solution using finite automata; ... 2.1 Combined Problems.
Size Complexity of Two-Way Finite Automata
blank symbol we accept iff the answer in (i) is “yes” for at least one node. In contrast
Finite Automata MCQ [Free PDF] - Objective Question Answer for
9 fév 2023 · Get Finite Automata Multiple Choice Questions (MCQ Quiz) with answers and detailed solutions Download these Free Finite Automata MCQ Quiz
[PDF] Finite Automata
My recommendation is to quickly figure out what your strengths and weaknesses are and focus your studying efforts on the areas in which
[PDF] QUESTION BANK Unit 1 Introduction to Finite Automata
QUESTION BANK Unit 1 Introduction to Finite Automata 1 Obtain DFAs to accept strings of a's and b's having exactly one a (5m )(Jun-Jul 10)
[PDF] 2 marks questions with answers & 16 mark questions
UNIT I AUTOMATA 2 MARKS QUESTION AND ANSWERS 1 What is deductive proof? NFA or Non Deterministic Finite Automaton is the one in which there exists
[PDF] Regular Languages and Finite Automata
1 REGULAR EXPRESSIONS The answer to question (a) on Slide 9 is 'yes' Algorithms for deciding such pattern- matching questions make use of finite automata
[PDF] Solutions to the exercises on Finite Automata
Find a deterministic finite-state automaton that recognizes the same language as the nondeter- ministic finite-state automaton in Exercise 19 Solution Let
[PDF] Finite Automata - Stony Brook Computer Science
24 jan 2021 · Solution The DFA accepts the string bbab The computation is: 1 Start in state q0 2 Read b follow transition from q0 to q1
[PDF] 1 Introducing Finite Automata
Solution • Build DFA M for L = {w there are uv s t w = usv} • Run M on text T Time = time to build M + O(t)! Questions 9 Page 10 • Is L regular no
(PDF) Answers to Questions Formulated in the Paper On States
PDF This paper gives answers to questions formulated as open in the paper "On State Observability in Deterministic Finite Automata" by A Mateescu and
Lecture Notes on
Regular Languages
and Finite Automata for Part IA of the Computer Science TriposMarcelo Fiore
Cambridge University Computer Laboratory
First Edition 1998.Revised 1999, 2000, 2001, 2002, 2003, 2005, 2006, 2007, 2008, 2009, 2010. c2010 A. M. Pitts
ContentsLearning Guideii
1 Regular Expressions1
1.1 Alphabets, strings, and languages . . . . . . . . . . . . . . . . . .. . . . . . 1
1.2 Pattern matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Some questions about languages . . . . . . . . . . . . . . . . . . . . .. . . 6
1.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Finite State Machines11
2.1 Finite automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Determinism, non-determinism, and-transitions . . . . . . . . . . . . . . . 14
2.3 A subset construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 17
2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3 Regular Languages, I23
3.1 Finite automata from regular expressions . . . . . . . . . . . .. . . . . . . . 23
3.2 Decidability of matching . . . . . . . . . . . . . . . . . . . . . . . . . .. . 28
3.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4 Regular Languages, II31
4.1 Regular expressions from finite automata . . . . . . . . . . . . .. . . . . . 31
4.2 An example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.3 Complement and intersection of regular languages . . . . .. . . . . . . . . . 34
4.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5 The Pumping Lemma39
5.1 Proving the Pumping Lemma . . . . . . . . . . . . . . . . . . . . . . . . . .40
5.2 Using the Pumping Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.3 Decidability of language equivalence . . . . . . . . . . . . . . .. . . . . . . 44
5.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6 Grammars47
6.1 Context-free grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 47
6.2 Backus-Naur Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.3 Regular grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
6.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
iiLearning GuideThe notes are designed to accompany six lectures on regular languages and finite automata
for Part IA of the Cambridge University Computer Science Tripos. The aim of this short course will be to introduce the mathematical formalisms of finite state machines, regular expressions and grammars, and to explain their applications to computer languages. As such, it covers some basic theoretical material which Every Computer Scientist Should Know. Direct applications of the course material occur in the various CST courses on compilers. Further and related developments will be found in the CST Part IB coursesComputation TheoryandSemantics of Programming Languagesand the CST Part II courseTopics inConcurrency.
This course contains the kind of material that is best learned through practice. The books mentioned below contain a large number of problems of varying degrees of difficulty, and some contain solutions to selected problems. A few exercises are given at the end of each section of these notes and relevant past Tripos questions are indicated there. At the end of the course students should be able to explain how to convert between the three ways of representing regular sets of strings introduced in the course; and be able to carry out such conversions by hand for simple cases. They should also be able to prove whether or not a given set of strings is regular. Recommended booksTextbooks which cover the material in this course also tend to cover the material you will meet in the CST Part IB courses onComputation Theoryand Complexity Theory, and the theory underlying parsing in various courses on compilers. There is a large number of such books. Three recommended onesare listed below. J. E. Hopcroft, R. Motwani and J. D. Ullman,Introduction to Automata Theory, Languages, and Computation, Second Edition(Addison-Wesley, 2001). D. C. Kozen,Automata and Computability(Springer-Verlag, New York, 1997). T. A. Sudkamp,Languages and Machines(Addison-Wesley Publishing Company,Inc., 1988).
NoteThe material in these notes has been drawn from several different sources, including the books mentioned above and previous versions of this course by the author and by others. Any errors are of course all the author's own work. A list of corrections will be available from the course web page. Please take time to fill out the on-line lecture feedback form.Marcelo Fiore
Marcelo.Fiore@cl.cam.ac.uk
11 Regular Expressions
Doubtless you have used pattern matching in the command-line shells of various operating systems (Slide 1) and in the search facilities of text editors. Another important example of the same kind is the `lexical analysis' phase in a compiler during which the text of a program is divided up into the allowed tokens of the programming language. The algorithms which implement such pattern-matching operations make use of thenotion of afinite automaton (which is Greeklish forfinite state machine). This course reveals (some of!) the beautiful theory of finite automata (yes, that is the plural of `automaton') and their use for recognising when a particular string matches a particular pattern.Pattern matching
What happens if, at a Unix/Linux shell prompt, you type ls and press return? Suppose the current directory contains files calledregflatex, regflaaux,regflalog,regfladvi, and (strangely)aux. What happens if you type lsaux and press return?Slide 1
1.1 Alphabets, strings, and languages
The purpose of Section 1 is to introduce a particular language for patterns, calledregular expressions, and to formulate some important problems to do with pattern-matching which will be solved in the subsequent sections. But first, here is some notation and terminology to do with character strings that we will be using throughout the course.21 REGULAR EXPRESSIONS
Alphabets
Analphabetis specified by giving a finite set,Σ, whose elements are calledsymbols. For us, any set qualifies as a possible alphabet, so long as it is finite.Examples:
1=0123456789-10-element set of decimal digits.
2=-26-element set of lower-case characters of the
English language.
3=Σ1-210-element set of all subsets of the alphabet of
decimal digits.Non-example:
N=0123- set of all non-negative whole numbers is not an alphabet, because it is infinite.Slide 2
Strings over an alphabet
Astring of length(0) over an alphabetΣis just an ordered-tuple of elements ofΣ, written without punctuation. Example:ifΣ =, then,,, andare strings overΣof lengths one, two, three and four respectively. def=set of all strings overΣof any finite length. N.B. there is a unique string of length zero overΣ, called thenull string (orempty string) and denoted (no matter whichΣwe are talking about).Slide 3
1.1 Alphabets, strings, and languages3
Concatenation of strings
Theconcatenationof two stringsΣis the stringobtained by joining the strings end-to-end.Examples:If=,=and=, then=,=
and=. This generalises to the concatenation of three or more strings.E.g.=.
Slide 4
Slides 2 and 3 define the notions of analphabetΣ, and the setΣof finitestringsover an alphabet. The length of a stringwill be denoted bylength(). Slide 4 defines the operation ofconcatenationof strings. We make no notational distinction between a symbolΣand the corresponding string of length one overΣ: soΣcan be regarded as a subset ofΣ. Note thatΣis never empty-it always contains thenull string,, the unique string of length zero.Note also that for anyΣ
==and()==() andlength() =length() +length().Example 1.1.1.Examples ofΣfor differentΣ:
(i) IfΣ =, thenΣcontains (ii) IfΣ =, thenΣcontains (iii) IfΣ =(theempty set- the unique set with no elements), thenΣ=, the set just containing the null string.41 REGULAR EXPRESSIONS
1.2 Pattern matching
Slide 5 defines the patterns, orregular expressions, over an alphabetΣthat we will use. Each such regular expression,, represents a whole set (possibly an infinite set) of strings inΣthatmatch. The precise definition of this matching relation is given onSlide 6. It might seem odd to include a regular expressionthat is matched by no strings at all-but it is technically convenient to do so. Note that the regular expressionis in fact equivalent to , in the sense that a stringmatchesiff it matches(iff=).Regular expressions over an alphabetΣ
each symbolΣis a regular expression is a regular expression is a regular expression ifandare regular expressions, then so is() ifandare regular expressions, then so is ifis a regular expression, then so is() Every regular expression is built up inductively, byfinitely many applications of the above rules. (N.B. we assume,,(,),, andarenotsymbols inΣ.)Slide 5
Remark 1.2.1(Binding precedence in regular expressions).In the definition on Slide 5 we assume implicitly that the alphabetΣdoes not contain the six symbols Then, concretely speaking, the regular expressions overΣform a certain set of strings over the alphabet obtained by adding these six symbols toΣ. However it makes things more readable if we adopt a slightly more abstract syntax, dropping as many brackets as possible and using the convention that binds more tightly than??, binds more tightly than??.So, for example,means(()), not()(), or(()), etc.
1.2 Pattern matching5
Matching strings to regular expressions
matchesΣiff= matchesiff= no string matches matchesiffmatches eitheror matchesiff it can be expressed as the concatenation of two strings,=, withmatchingandmatching matchesiff either=, ormatches, orcan be expressed as the concatenation of two or more strings, each of which matchesSlide 6
The definition of `matches' on Slide 6 is equivalent to saying for some0,can be expressed as a concatenation ofstrings,=12, where eachmatches.
Thecase= 0justmeansthat=(soalways matches); andthecase= 1justmeans thatmatches(so any string matchingalso matches). For example, ifΣ = and=, then the strings matchingare etc Note that we didn't include a regular expression for the `' occurring in the UNIX examples on Slide 1. However,once we know which alphabet we are referring to,Σ =12say, we can get the effect ofusing the regular expression
(12) whichisindeedmatchedby anystringinΣ(because12ismatchedby anysymbol inΣ).61 REGULAR EXPRESSIONS
Examples of matching, withΣ =01
01is matched by each symbol inΣ
1(01)is matched by any string inΣthat starts with a `1'
((01)(01))is matched by any string of even length inΣ (01)(01)is matched by any string inΣ (0)(1)11is matched by just the strings,0,1,01, and1110is just matched by0
Slide 7
Notation 1.2.2.The notation+is quite often used for what we write as. The notation, for0, is an abbreviation for the regular expression obtained by concatenatingcopies of. Thus: 0def= +1def=()Thusmatchesiffmatchesfor some0.
We use+as an abbreviation for. Thusmatches+iff it can be expressed as the concatenation ofone or morestrings, each one matching.1.3 Some questions about languages
Slide 8 defines the notion of aformal languageover an alphabet. We take a very extensional view of language: a formal language is completely determined by the `words in the dictionary', rather than by any grammatical rules. Slide 9 gives some important questions about languages, regular expressions, and the matching relation between strings and regular expressions.1.3 Some questions about languages7
Languages
A (formal)languageover an alphabetΣis just a set of strings inΣ. Thus any subsetΣdetermines a language overΣ. Thelanguage determined by a regular expressionoverΣis ()def=Σmatches Two regular expressionsand(over the same alphabet) are equivalentiff()and()are equal sets (i.e. have exactly the same members).Slide 8
Some questions
(a) Is there an algorithm which, given a stringand a regular expression (over the same alphabet), computes whether or notmatches? (b) In formulating the definition of regular expressions, have we missed out some practically useful notions of pattern? (c) Is there an algorithm which, given two regular expressionsand (over the same alphabet), computes whether or not they are equivalent? (Cf. Slide 8.) (d) Is every language of the form()?Slide 9
81 REGULAR EXPRESSIONS
The answer to question (a) on Slide 9 is `yes'. Algorithms fordeciding such pattern- matchingquestionsmakeuseof finiteautomata. Wewill seethis duringthe nextfew sections. If you have used the UNIX utilitygrep, or a text editor with good facilities for regular expression based search, likeemacs, you will know that the answer to question (b) on Slide 9 is also `yes'-the regular expressions defined on Slide 5 leave out some forms of pattern that one sees in such applications. However, the answer to the question is also `no', in the sense that (for a fixed alphabet) these extra forms of regularexpression are definable, up to equivalence, from the basic forms given on Slide 5. For example, if the symbols of the alphabet are ordered in some standard way, it is common to provide a form of pattern for naming ranges of symbols-for example[a?z]might denote a pattern matching any lower- case letter. It is not hard to see how to define a regular expression (albeit a rather long one) which achieves the same effect. However, some other commonly occurring kinds of pattern are much harder to describe using the rather minimalist syntax of Slide 5. The principal example iscomplementation,(): matches()iffdoes notmatch. It will be a corollary of the work we do on finite automata (and agood measure of its power) that every pattern making use of the complementation operation(?)can be replaced by an equivalent regular expression just making use of the operations on Slide 5. But why do we stick to the minimalist syntax of regular expressions on that slide? The answer is that it reduces the amount of work we will have to do to show that, in principle, matching strings against patterns can be decided via the use of finite automata. The answer to question (c) on Slide 9 is `yes' and once again this will be a corollary of the work we do on finite automata. (See Section 5.3.) Finally, the answer to question (d) is easily seen to be `no',provided the alphabetΣ containsatleastonesymbol. ForinthatcaseΣiscountablyinfinite; andhencethenumberof languages overΣ, i.e. the number of subsets ofΣis uncountable. (Recall Cantor's diagonal argument.) But sinceΣis a finite set, there are only countably many regular expressions overΣ. (Why?) So the answer to (d) is `no' for cardinality reasons.However, even amongst the countably many languages that are `finitely describable' (an intuitive notion that we will not formulate precisely) many are not of the form()for any regular expression. For example, in Section 5.2 we will use the `Pumping Lemma' to seethat 0 is not of this form.1.4 Exercises
Exercise 1.4.1.Write down an ML data type declaration for a type constructor"a regExp whose values correspond to the regular expressions over an alphabet"a. Exercise 1.4.2.Find regular expressions over01that determine the following languages: (a)contains an even number of1's1.4 Exercises9
(b)contains an odd number of0's Exercise 1.4.3.For which alphabetsΣis the setΣof all finite strings overΣitself an alphabet? Tripos questions2005.2.1(d) 1999.2.1(s) 1997.2.1(q) 1996.2.1(i) 1993.5.12101 REGULAR EXPRESSIONS
112 Finite State Machines
We will be making use of mathematical models of physical systems calledfinite automata, orfinite state machinesto recognise whether or not a string is in a particular language.quotesdbs_dbs8.pdfusesText_14[PDF] finite state automata
[PDF] finland emergency medical services
[PDF] fintech 2019
[PDF] fintech in india
[PDF] fintech investment in india 2019
[PDF] fintech ranking
[PDF] fintech startups
[PDF] fip travel
[PDF] fipy: partial differential equations with python
[PDF] fir and iir filters pdf
[PDF] fir copy sample
[PDF] fir filter applications ppt
[PDF] fir filter design
[PDF] fir filter design matlab