2) Give a DFA (both state transition diagram and table as well as description of each state) for each of the following languages a) A language over alphabet E = {0,1,2,3,4,5,6,7} in which reverse of each string (for instance, reverse of 1234 is 4321) interpreted as an octadecimal (base-8) number is a multiple of 3. (for example: 14, 47, 135, 512, 702, 4001, 41713, e.t.c) (Hint: Consider inductive contruction wnew = wold:a which means wverse = %3D erse, where a denotes any symbol from E and then try to figure out the states of DFA with respect to possible values of a and the length of wola-) a. Wold

2) Give a DFA (both state transition diagram and table as well as description of each state) for each of the following languages a) A language over alphabet E = {0,1,2,3,4,5,6,7} in which reverse of each string (for instance, reverse of 1234 is 4321) interpreted as an octadecimal (base-8) number is a multiple of 3. (for example: 14, 47, 135, 512, 702, 4001, 41713, e.t.c) (Hint: Consider inductive contruction wnew = wold:a which means wverse = %3D erse, where a denotes any symbol from E and then try to figure out the states of DFA with respect to possible values of a and the length of wola-) a. Wold

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

Give the state diagrams of DFAs recognizing the following languagesover Σ = {0, 1}:a. {w : w does not contain substring 10}b. {w : every odd position of w is a 1}c. {w : w contains at least one 0 and at least one 1}
For each of the languages below, draw a transition diagram for a DFA which accepts thatlanguage.(a) Strings over Σ = {a, b, c} which begin with the character a and end with the character c.(b) Strings over Σ = {a, b} in which the characters a and b always alternate. For example, stringsababa, bab, and a are in this language.(c) Strings over Σ = {a, b} which end with either aa or bb.(d) Strings over Σ = {0, 1, 2}, such that the sum of all digits in the string is divisible by 4.For example, the string 02101 is in the language because 0 + 2 + 1 + 0 + 1 = 4, which is divisible by 4;but 1212 is not, because 1 + 2 + 1 + 2 = 6 is not divisible by 4.
2) Give a DFA (both state transition diagram and table as well as description of each state) for each of the following languages a) A language over alphabet E = {0,1,2,3,4,5,6,7} in which reverse of each string (for instance, reverse of 1234 is 4321) interpreted as an octadecimal (base-8) number is a multiple of 3. (for example: 14, 47, 135, 512, 702, 4001, 41713, e.t.c) (Hint: Consider inductive contruction wnew = wold a which means whewe a. wgerse, where a denotes any symbol from E and then try to figure out the states of DFA with respect to possible values of a and the length of wold-) reverse
Design the NFA N for language L = {w | the first symbol of w is different from the last symbol and the second symbol of w is also different from the last symbol} which is defined over the alphabet {0,1}. Draw the state transition diagram for N. Give the formal 5-tuple definition of N.
Design the NFA N for language L = {w | the first symbol of w is different from the last symbol, but the second symbol of w is the same as the last symbol} which is defined over the alphabet {0,1}. (hint: think about |w|=2 too) a) Draw the state transition diagram for N. b)Give the formal 5-tuple definition of N.
Given: Language L2 = {w ϵ {a,b}* | w contains substring aab} Construct the DFA representing the given language L2. Assume the layout of the DFA is as follows: ->A->B->C->D*. That is, the number of states are four (4) and A is the starting state and D is the accepting state. What is the next state for the input pair (D,b) in the constructed DFA? A B C D
Construct a DFA/NFA with three states that accepts the language L defined over the alphabet (a, b, c) as follows: L = {ab, abc}*
Give the CFG of the following language over the alphabet {a, c, d}: The language contains the substring ccccExamples:dacdccccad, ccccda, adcccc, cdccccc
Briefly explain the following languages are NOT decidable. ETM = {{M>| M is a TM and L(M) = Ø}. The complement of ETM 8.
Construct DFAs for the following languages. Give both the state diagrams and the state-transition tables. The set of binary strings that start with “11” and end with “01”. Σ = {0,1,2} The set of binary strings which, when converted into an integer number, are divisible by 6. The string must not have leading zeros (for example, 110, 0, and 11110 will be accepted, 0110, 1111, and 101 will be rejected). Empty string (ϵ) will be rejected. (Σ = {0,1} The set of binary strings whose length is odd and has 1 in every even position. (The strings 0 and 1 will also be accepted by the DFA). Σ={0,1}. For example: 010, 01111, 11010, 1111010, etc. The set of binary strings that do not contain exactly two 0’s. (it may have more than 2 0’s, or less). Empty string (ϵ) will be accepted. Σ = {0,1} The set of binary strings with even numbers of 0’s and with 1’s in pairs. Σ = {0,1}. For example: ϵ, 11, 00, 1111, 0110, 110110, 01100110.
1. In your own words, list and explain each step to convert a context-free language to Chomsky Normal Form. At each step give a simple example. Do NOT write a full CNF conversion. A simple example of substitution might be as follows: original: A->aBa, B-> b/c substitution: A-> aba / aca
Given the language L-b*(alb)a*a, draw and upload the FA (DFA or NFA or NFA-E).