Computer Science QUESTIONa) The grammar G is described by its vocabulary V = {a, b, c, A}, Production P ={A → ab, A - abc, A → abcA}, and Terminal symbols TWhat language L (G) is generated by G?{a, b, c}.b) Draw a transition diagram of a finite-state automaton that accepts any strings over {1,0}, which begins with odd number of 1 and ends with even number of 0. An exampleof an accepted string is 11100.

a) The grammar G is described by its vocabulary V = {a, b, c, A}, Production P = {A - ab, A - abc, A → abcA}, and Terminal symbols T = {a, b, c}. What language L (G) is generated by G? %3D b) Draw a transition diagram of a finite-state automaton that accepts any strings over {1, 0}, which begins with odd number of 1 and ends with even number of 0. An example of an accepted string is 11100.

a) The grammar G is described by its vocabulary V = {a, b, c, A}, Production P = {A - ab, A - abc, A → abcA}, and Terminal symbols T = {a, b, c}. What language L (G) is generated by G? %3D b) Draw a transition diagram of a finite-state automaton that accepts any strings over {1, 0}, which begins with odd number of 1 and ends with even number of 0. An example of an accepted string is 11100.

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

Consider a grammar for expressions is defined as follows:<assign> → <id> = <expr><id> → A | B | C | D<expr> → <id> + <expr>| <id> * <expr>| ( <expr> )| <id>Give a recursive descent algorithm for the BNF defined above.You may abstract away some details and are expected to make your answer using pseudo code.
This question is about context-free grammars and parsing, and Turing machines (TM’s). Question 1) Consider the following context-free grammar G over the alphabet Σ = {a, b, c}: S → aSb | ε | acSba | abc Using any of the grammar transformation techniques we saw in this module, construct a CNFgrammar that generates the same language as the grammar G of Question 1.Make sure you include in your answer all individual steps that you followed. Please help me with this question :)
Let G = (V, E, R, S) be a grammar with V= {S, H, Gm J}; = {h, g. j}; and the set of rules: H>h | hJG G> Gg | Sg | HgJ J→ jH | HHJ| Jj Convert this grammar to a PDA using the method we described.
L={a"b"a" | n,m=1,2,3.} is given. i) Write a CFG for the language L. ii) Construct a push down automata (PDA) model that accepts L. (PLEASE USE THE NOTATION GIVEN IN THE TEXTBOOK WHILE DRAWING THE PDA, PDA's CONSTRUCTED USING OTHER NOTATIONS WILL NOT BE EVALUATED.) iii) Show the leftmost derivation for the string aaaabbbaaaa. iv) Draw the derivation tree for the string aaaabbbaaaa.
What is the length of an empty string? * Which is described as a set of symbols? * O Alphabet O String O Formal Language Let G be a formal grammar with the following production rules: Sigma - 1A, A --> OB, B --> OB, B--> O. Sigma is referring to the Greek symbol for capital Sigma. Assume that the conventions in the presentation of Grammar as discussed in our course are followed, give one element of the set of nonterminal symbols for grammar G. * Your answer
2. If L is a regular language over E, what can be said about the languages L1 = E* – L and L2 = reverse(L*)? A. Li is always regular but not L2. B. L2 is always regular but not L1. C. Li and L2 are both regular. 3. What is the language generated by the grammar G: { S → aR , R → aR| baR|b }? A. (aa*b)* B. (a*b)(a*b)* C. (aa*b)(aa*b)* 4. IfL is a regular language over some alphabet E, what can be said about the language L’ = (E* – L) N reverse(L)? A. L' is surely regular. B. L’ is surely non-regular. C. Its type cannot be determined without additional information. 5. Including the trap state, how many states are there in the minimum-state DFA for the regular expression (a+b)*(b+c)* ? Also how many final states will there be in the minimum-state DFA? A. 4 states with one final state B. 3 states with two final states C. 3 states with one final state
Let ANTIPALINDROME be the language of all even-length strings over the alphabet {a,b} such that, for all i, the i-th letter from the start is different to the i-th letter from the end. Examples of strings in this language include: ε, ab, ba, aabb, abab, baba, bbaa, aaabbb, ... Give a Context-Free Grammar for the language ANTIPALINDROME.
L = {am+n bm cn | m,n ≥ 1} over Σ = {a, b, c} A. Design PDA for L (with as less as states possible) B. Is L is regular language? C. Verify it by Pumping Lemma
5. Consider languages over terminal alphabet Σ = {a,b,c,d}. Give context-free grammars that generate the following five languages. • In each case, also give a derivation of the specified terminal string using your gram- mar. The derivation beginning from the start variable should indicate each individual derivation step using the notation ⇒. (a) L₁ = {b²i³k+¹ | k ≥ i ≥ 0} Derivation for the string: 6²c4. (b) L₂ = { a¹bk c²i | i ≥ 1, k ≥ 1} U {c³k dk | k ≥ 1} Derivation for the string: a²bc². (c) L3 = {a²if²i+1c5k+2 | i ≥ 1, k ≥ 1} Derivation for the string: a¹b³c7. (d) L₁ = = {a²f³i+1³s+1di+¹ | i ≥ 1, r ≥ 1, s ≥ 1} Derivation for the string: 2r a¹b¹c²d² (e) L5 = {a³i+¹f²+3 ¿2k d²k | i ≥ 0, k ≥ 0} U {a²¹b³c³³d²+¹ | r ≥ 0, s ≥ 0} Derivation for the string: a²bc5d².
NAT Lang processing: Please explain in detail Consider a CFG representing a phrase structure grammar for a natural language such as English, including the following rule (the period is part of the rule): S -> NP VP . In this rule, S, NP, and VP are non-terminal symbols, but we will assume that the period is a terminal symbol specifically representing a period (as opposed to some other end-of-sentence marker). So, we can interpret this rule as stating that a sentence can have the form of a noun phrase followed by a verb phrase followed by a period. (To implement a parser for grammars with rules like this, the tokenizer would have to treat periods as separate tokens.) Assume that you need to convert this grammar to Chomsky normal form (CNF), perhaps with the CKY parsing algorithm in mind. Using the procedure discussed in class, show the rules that might result from the conversion.
Predictive parsers are recursive descent parsers that need no backtracking and can be constructed for a class of grammars called LL (1). The first "L" in LL (1) indicates that, scanning the input from left to right. The second "L" in LL (1) signifies that, producing a leftmost derivation. The "1" in LL (1) indicates that, using one input symbol of lookahead at each step to make parsing action decisions. Like recursive descent, the LL (1) technique is top-down, goal oriented, and predictive. Consider the grammar G5: S → iEtSS′|a S′ → eS|ԑ E → bConstruct the LL (1) parsing table for the grammar G5 and use the LL (1)parsing table for the grammar G5 to check whether the grammar G5 is LL (1). Algorithm sheet: Algorithm for Constructing LL (1) Parsing Table Input: Grammar G.Output: Parsing table M.Method: For each production A → a of the grammar, do the following: Step 1: For each terminal "a" in ????? (a), add A → a to M[A, a].Step 2: If ? is in ????? (a), then for each terminal b in…
4. Write a regular expression (RE) to define the language of all strings that start with 'bb' and contain the substring 'aa' and finish with 'a'. 5. Give a Push Down Automaton (PDA) to decide the language { arban+1 /n>=0} 6. Give a Context Free Grammar (CFG) to define the language { arb2n+1 /n>=0} 7. Give a Turing machine to decide the language: {w in {a,b}* / w starts with "aa" and ends with "ba"}