1.6 Give state diagrams of DFAs recognizing the following languages. In all alphabet is {0,1}. parts, the a. {w w begins with a 1 and ends with a 0} b. {ww contains at least three 1s} c. {ww contains the substring 0101 (i.e., w = x0101y for some x and y)} d. {w w has length at least 3 and its third symbol is a 0} e. {w w starts with 0 and has odd length, or starts with 1 and has even length} f. {w w doesn't contain the substring 110} g. {w the length of w is at most 5} h. {w w is any string except 11 and 111}

1.6 Give state diagrams of DFAs recognizing the following languages. In all alphabet is {0,1}. parts, the a. {w w begins with a 1 and ends with a 0} b. {ww contains at least three 1s} c. {ww contains the substring 0101 (i.e., w = x0101y for some x and y)} d. {w w has length at least 3 and its third symbol is a 0} e. {w w starts with 0 and has odd length, or starts with 1 and has even length} f. {w w doesn't contain the substring 110} g. {w the length of w is at most 5} h. {w w is any string except 11 and 111}

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

1.6 Give state diagrams of DFAS recognizing the following languages. In all parts the alphabet is {0,1} a. {w| w begins with a 1 and ends with a 0} b. {w w contains at least three 1s} c. {w w contains the substring 0101, i.e., w = r0101y for some r and y} d. {w w has length at least 3 and its third symbol is a 0} e. {w w starts with O and has odd length, or starts with 1 and has even length} f. {w w doesn't contain the substring 110} g. {w the length of w is at most 5} h. {ww is any string except 11 and 111} i. {w every odd position of w is a 1} j. {w w contains at least two Os and at most one 1} k. {e,0} 1. {w w contains an even number of Os, or contains exactly two 1s} m. The empty set n. All strings except the empty string
2.12. For each of the following languages, draw an FA accepting it. la. b)*{a) b. (bb, ba)* c. (a, b}* {b, aa}{a, b)* d. (bbb, baa}* (a} e. (a} U (b}{a}* U (a)(b)* (a) f la, b)*(ab, bba) g. (b, bba)* (a) h. (aba, aa)* {ba}*
2.12. For each of the following languages, draw an FA accepting it. d. (bbb, baa}* (a) e. (a} U (b}{a}* U (a}(b}* (a) f (a, b)* (ab, bba) g. (b, bba}* (a} h. (aba, aa)* (ba)*
1. For each of the following regular expressions find a language (i.e., a set of strings) over A = {a,b,c} that can be represented/described by that expression. a. a*bc + bc* b. b*aaac* а. b.
8. Build a DPDA that accepts the language L = {(ab)" (aab)b² n ≥0
Given: Language L3 = {w ϵ {a,b}* | w starts in ab and ends in bb} Construct the DFA representing the given language L3. Assume the layout of the DFA is as follows: ->A->B->C->D->E*. That is, the number of states are five (5) and A is the starting state and E is the accepting state. What is the next state for input pair (D,a) in the constructed DFA?
Given: Language L3 = {w ϵ {a,b}* | w starts in ab and ends in bb} Construct the DFA representing the given language L3. Assume the layout of the DFA is as follows: ->A->B->C->D->E*. That is, the number of states are five (5) and A is the starting state and E is the accepting state. What is the next state for input pair (E,a) in the constructed DFA? ABCDE choices
5) Give state diagrams of DFAs recognizing the following languages. In all parts the alphabet is {0, 1} a. {w w begins with a 1 and ends with a 0} b. {ww contains at least three ls} c. {ww contains the substring 0101} d. {w w has length at least 3 and its third symbol is a 0} e. {ww starts with 0 and has odd length, or starts with 1 and has even length} f. {w w doesn't contain the substring 110} g. {w the length of w is at most 5} h. {ww is any string except 11 and 111} i. {w | every odd position of w is a 1}
Write a regular expression to describe each of the following languages. Example: {w € {a, b}* : w has both aa and bb as substrings} Regular expression: (a U b)* aa (a U b) bb (a U b) U (a U b)* bb (a U b)* aa (a U b)*
Write a regular expression to describe each of the following languages. Example: {w = {a, b}* : w has both aa and bb as substrings} Regular expression: (a U b)* aa (a U b)* bb (a U b)* U (a U b)* bb (a U b)* aa (a U b)*
Write a CFG to represent the expressions of a programming language with following characteristics: • The language supports addition (+) and multiplication (*) operations only. The language allows only two alphabets a and b, and two digits 0 and 1.. The identifiers must begin with a or b, followed by any string in {a, b, 0, 1)*.
1.7 Give state diagrams of NFAS with the specified number of states recognizing each of the following languages. In all parts, the alphabet is {0.1}. Aa. The language {w w ends with 00} with three states b. The language of Exercise 1.6c with five states c. The language of Exercise 1.61 with six states d. The language {0} with two states c. {ww contains the substring 0101 (i.e., w = r0101y for some r and y)} L {ww contains an even number of Os, or contains exactly two 1s}