Question

1. a) Rewrite the following rule base as a CFG and provide its formal definition ( S is the start

state )

S → aSb | bAA

A → b {aB} | a | Bc

B → aB | c

b) Generate the 10 smallest possible strings using the above rule base. ( from problem a)

2. Either show that the following strings are in this language
or state why these strings **can**

**not be..**

S → AB | BC | cB

A → Ac | aBB | b

B → Cb | cBb | a

C → Ac | bCA | c

a) aCbcBbcBb b) ccbcbbb b) cabbCA

Answer #1

**solution:**

**given
data:**

1).

**a)**

Context-free grammar

A context-free grammar is a formal grammar that is used to generate all possible strings in a given formal language.

Context-free grammar G can be defined by four tuples as:

- G= (V/N, T, P, S)

Where,

G describes the grammar

T describes a finite set of terminal symbols.

V/N describes a finite set of variables or non-terminal symbols

P describes a set of production rules

S is the start symbol.

In CFG, the start symbol is used to derive the string. You can derive the string by repeatedly replacing a non-terminal by the right-hand side of the production, until all non-terminal have been replaced by terminal symbols.

Example:

consider given productions are:

S → aSb | bAA

A → b {aB} | a | Bc

B → aB | c

Now check that abaccb string can be derived from the given CFG.

S →aSb

S →abAAb

S →abaAb

S →abaBcb

S →abaccb

By applying the production recursively and finally applying the production B → c, we get the string abaccb.

**b)**

10 smallest possible strings

= {baa, bacc, bcca, bcccc, abaab, baacc, abaccb, abccab, bccacc, bacccc }

**please give me thumb up**

Automata Theory and Formal Languages
Problems 1: Consider the following two
grammars.
Grammar G1- S → aSb / ∈ Grammar G2- S → aAb / ∈, A → aAb / ∈
a. is G1=G2
b. What is the grammar generated by the expression
Problem 2: Let us consider the grammar.
G2 = ({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε } )
Derive aaabbb
Problem 3: Suppose we have the following
grammar.
G: N...

1. Which of the following is the correct definition of
synteny
a) The conservation of gene order within two genomes
b) The conservation of gene function within two genomes
c) The percentage of nucleotide sequence identity between two
genomes
d) The percentage of amino acid sequence identity between two
genomes
2. Why is open reading frame scanning not applicable when
searching for functional RNA genes?
a. the codons for functional RNA molecules are not well
understood
b. introns make the...

Please answer the following Case
analysis questions
1-How is New Balance performing compared to its primary rivals?
How will the acquisition of Reebok by Adidas impact the structure
of the athletic shoe industry? Is this likely to be favorable or
unfavorable for New Balance?
2- What issues does New Balance management need to address?
3-What recommendations would you make to New Balance Management?
What does New Balance need to do to continue to be successful?
Should management continue to invest...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 17 minutes ago

asked 38 minutes ago

asked 40 minutes ago

asked 53 minutes ago

asked 56 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago