Consider the following context-free grammar over the alphabet ∑ = {a, b, c} with S as the start symbol: S → abScT | abcT T → bT | b Which one of the following represents the language generated by the above grammar?

{(ab)ⁿ (cb)ⁿ | n ≥ 1}
{(??)^? ??^?¹ ??^?²… ??^?^?|?, ?₁, ?₂… , ?_? ≥ 1}
{(ab)ⁿ (cb^m)ⁿ | m, n ≥ 1}
{(ab)ⁿ (cbⁿ)^m | m, n ≥ 1}

LohaHridoy

4 views

2025-01-04 04:42

1 Answers

AhmedNazir

Option 2 : {(𝑎𝑏)𝑛 𝑐𝑏𝑚1 𝑐𝑏𝑚2 … 𝑐𝑏𝑚𝑛 |𝑛, 𝑚1, 𝑚2 … , 𝑚𝑛 ≥ 1}

String Derivation:

S → abScT

→ ababScTcT (∵ S → abScT)

→ abababcTcTcT (∵ S → abcT)

→ abababcbTcTcT (∵ T → bT)

→ abababcbbTcTcT (∵ T → bT)

→ abababcbbbTcTcT (∵ T → bT)

→ abababcbbbbcTcT (∵ T → b)

→ abababcbbbbcbcT (∵ T → b)

→ abababcbbbbcbcbT (∵ T → bT)

→ abababcbbbbcbcbb (∵ T → b)

abababcbbbbcbcbb = (ab)³cb⁴cbcb²

From this string, it is clear that all the option 1),3) and 4) are not generated by given grammar.

Only option 2 matches.

4 views Answered 2022-09-04 04:29

Related Questions

Consider the language L = {an |n ≥ 0} ∪ {anbn| n ≥ 0} and the following statements. I. L is deterministic context-free. II. L is context-free but not deterministic context-free. III. L is not LL(k) for any k. Which of the above statements is/are TRUE?

1 Answers 4 Views

A student wrote two context-free grammars G1 and G2 for generating a single C-like array declaration. The dimension of the array is at least one. For example, int a[10] [3] ; The grammars use D as the start symbol, and use six terminal symbols int; id[ ] num Grammar G1 Grammar G2 D → int L; D → int L; L → id[E L → idE E → num] E → E[num] E → num][E E → [num] Which of the grammars correctly generate the declaration mentioned above?

1 Answers 4 Views

Language L1 is defined by the grammar: S1 → aS1b|ϵ Language L2 is defined by the grammar: S2 → abS2|ϵ Consider the following statements: P: L1 is regular Q: L2 is regular Which one of the following is TRUE?

1 Answers 4 Views

Consider the transition diagram of a PDA given below with input alphabet ∑ = {a, b} and stack alphabet Γ = {X, Z}. Z is the initial stack symbol. Let L denote the language accepted by the PDA. Which one of the following is TRUE?

1 Answers 4 Views

Consider the following languages L1 = {ap | p is a prime number} L2 = {anbmc2m | n ≥ 0, m ≥ 0} L3 = {anbnc2n | n ≥ 0} L4 = {anbn | n ≥ 1} Which of the following are CORRECT I. L1 is context-free but not regular. II. L2 is not context-free III. L3 is not context-free but recursive. IV. L4 is deterministic context-free?

1 Answers 5 Views

Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M. Which of the following decision problems are undecidable I. Given a regular expression R and a string w, is w ∈ L(R) II. Given a context-free grammar G, is L(G) = ϕ III. Given a context-free grammar G, is L(G) = ∑* for some alphabet ∑ IV. Given a Turing machine M and a string w, is w ∈ L(M) ?

1 Answers 4 Views

Let L1, L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT I. L1 ∪ L2 is context-free II. L̅1 is context-free III. L1 – R is context-free IV. L1 ∩ L2 is context-free?

1 Answers 5 Views

Consider the following sets: S1. Set of all recursively enumerable languages over the alphabet {0,1} S2. Set of all syntactically valid C programs S3. Set of all languages over the alphabet {0,1} S4. Set of all non-regular languages over the alphabet {0,1} Which of the above sets are uncountable?

1 Answers 6 Views

If ‘figure 1’ represents ‘Lux’, ‘figure 2’ represents ‘Herbal’, ‘figure 3’ represents ‘Dove’ and ‘figure 4’ represents ‘Shampoo’, then which alphabet represents ‘Herbal shampoo but neither lux nor dove’?

1 Answers 4 Views

If ‘figure 1’ represents ‘Tree’, ‘figure 2’ represents ‘Mango’ and ‘figure 3’ represents ‘Apple’, then which alphabet represents ‘Apple tree’?

1 Answers 4 Views

এক্সাম দিয়ে মেধা যাচাই করুন

Job Preparation (1125)

Admission (754)

এসএসসি (10)

এইচএসসি (5)