Given a regular grammar G = {{S, T, a, b}, {a, b}, R, S}, where R = {S→ E, SaT, S → bT, T → aS, T → bS}, the correct statements are: L(G) = {[w€ {a, b}*: |w| is odd}. L(G) = {w€ {a, b}*: |w| is even}. a*b* is a regular expression that generates L(G). Ob*a* is a regular expression that generates L(G).

Given a regular grammar G = {{S, T, a, b}, {a, b}, R, S}, where R = {S→ E, SaT, S → bT, T → aS, T → bS}, the correct statements are: L(G) = {[w€ {a, b}: |w| is odd}. L(G) = {w€ {a, b}: |w| is even}. ab is a regular expression that generates L(G). Oba is a regular expression that generates L(G).

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.
Q4: Let Σ = {0, 1, #} and define a language B over Σ as follows: B = {r#s: r,s = {0, 1}^*, r is a substring of s}. Prove that the language B is not context free
Create a PDA that accepts the language L = {w ∈ {a.b}* : na(v) ≥ nb(v), where v is any prefix of w}
subject theory of computer science Consider the following grammar G = {S, A}, S = {S}, ∑ = {a, b}, P : S → aS | aA; A → bA | b; Which of the following regular expression denotes L(G)? A.a(ab)*b B.a*b* C.aa*bb D.a*ab*b
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. How many self-loop edge/s in the constructed DFA representing the given language L2?
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.
Assumptions ... • Alphabet Σ = {a, b} . L₁= {ab n ≥ 0 An mod 3=0} L₂= {am: n ≥0^m≥ 0^n=m-1} ● . To do in this exercise ... Find a context-free grammar G such that L(G) = L₁ U L2. • Save your context-free grammar as a JFLAP .jff file, and submit that .jff file to Canvas as your solution to this exercise.
Given the following Regular Grammar (RG) StS zF F→ 2G|z G→tG|t Which of the following strings can be generated by it? i. tzz ii. ztt iii. ttzz iv. zztt O A. i, ii, and iii B. ii, iii, and iv O C. ii and iv O D. i and iii
Construct a CFG and PDA for the language B={w| w is a string over {a,b} with the same count of a's and b's}. For example, abba € B, abab e B,aabb € B, babbbaaaba € B, that is, there is no particular order in which a's and b's appear in w as long as there is the same amount of them.
Prove this grammar is Ambiguous <S> -> <A> <A> -> <A> + <A> | <id> <id> -> a | b | c
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. How many self-loop edge/s in the constructed DFA representing the given language L3? Don't give wrong answer. Upvote for only correct one else down
L = { w ? { a, b, c, d }*| na(w), nb(w), nc(w), nd(w) ≥ 0, na(w)+nc(w)+nd(w) < nb(w) } Is L a Context Free Language. Prove by creating PDA or by using Pumping Lemma