Resumen

COS3701 - Notes (Summary)

0 veces vendidas

Grado
COS3701 - Theoretical Computer Science III

Institución
University Of South Africa

COS3701 - Notes (Summary) S - The study-notes marketplace Context Free Language (CFL) CFL is a language generated by some Context Free Grammer(CFG) CFGs CFG formal definition: Nonterminals are capital letters and terminals (since they can terminate, i.e end) are small values. Example: So...

[Mostrar más]

Vista previa 4 fuera de 182 páginas

Ver ejemplo

Subido en 7 de mayo de 2022
Número de páginas 182
Escrito en 2021/2022
Tipo Resumen

cos3701 notes summary

Institución
University of South Africa
Grado
COS3701 - Theoretical Computer Science III

Seguir

Tutor23

Miembro desde 3 año 1861 documentos vendidos

117

3,24 €

Añadir al carrito

Añadir a la lista de deseos

100% de satisfacción garantizada
Inmediatamente disponible después del pago
Tanto en línea como en PDF
No estas atado a nada

COS3701 -
Notes
(Summary)

, Stuvia.com - The study-notes marketplace

Context Free Language (CFL)
CFL is a language generated by some Context Free Grammer(CFG)

CFGs
CFG formal definition:

Nonterminals are capital letters and terminals (since they can terminate, i.e end)
are small values.
Example:

So the general formulae is 𝑎𝑛 which is the language a*. Thus this CFG
generated the language a*. Remember a* means any certain number of a’s.
a* means any number of a’s. Can be 0 as well.

Note: -> is used in production and means ‘can be replaced by’ but the
double arrow means ‘çan develop into’.
Example:

Downloaded by: examsummaries29 |
Distribution of this document is illegal

, Stuvia.com - The study-notes marketplace

This is also the language a*. So both CFG’s in the 1 st example and 2 nd example
generated the language a*. This illustrated that more than 1 CFG can generate
the same language.
Example

The language generated by the CFG is the set of all possible strings of the
letters a and b except for the null string. Thus it is not (a+b)* because this
includes the null string.
In my own words: So we can start of with either making S aS or bS. Then again
we can replace that S with either aS or bS again for any number of times. Then
we can end it by replacing S with either a or b which makes the language all
possible strings of the letters a and b except for the null string.
Example

Downloaded by: examsummaries29 |
Distribution of this document is illegal

, Stuvia.com - The study-notes marketplace

From the start symbol S we can go to either X or Y. Notice then that X can only
produce the empty string .
Y can produce the same language as the previous example, i.e. all strings of a
and b excluding the empty string.

So adding then X production and Y productions then this CFG generates the
language (a+b)*. (a+b)* is any strings of a and b including the empty string .

Example

Also the word ab can be generated like this:
S=> aS
=>ab (S->b)

Downloaded by: examsummaries29 |
Distribution of this document is illegal

Los beneficios de comprar resúmenes en Stuvia estan en línea:

Garantiza la calidad de los comentarios

Compradores de Stuvia evaluaron más de 700.000 resúmenes. Así estas seguro que compras los mejores documentos!

Compra fácil y rápido

Puedes pagar rápidamente y en una vez con iDeal, tarjeta de crédito o con tu crédito de Stuvia. Sin tener que hacerte miembro.

Enfócate en lo más importante

Tus compañeros escriben los resúmenes. Por eso tienes la seguridad que tienes un resumen actual y confiable. Así llegas a la conclusión rapidamente!

Preguntas frecuentes

What do I get when I buy this document?

You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.

100% de satisfacción garantizada: ¿Cómo funciona?

Nuestra garantía de satisfacción le asegura que siempre encontrará un documento de estudio a tu medida. Tu rellenas un formulario y nuestro equipo de atención al cliente se encarga del resto.

Who am I buying this summary from?

Stuvia is a marketplace, so you are not buying this document from us, but from seller Tutor23. Stuvia facilitates payment to the seller.

Will I be stuck with a subscription?

No, you only buy this summary for 3,24 €. You're not tied to anything after your purchase.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

45,681 summaries were sold in the last 30 days

Founded in 2010, the go-to place to buy summaries for 15 years now

Empieza a vender

Resumen

COS3701 - Notes (Summary)

Información del documento

Temas

Escuela, estudio y materia

Vendedor

Comentarios recibidos

Vista previa del contenido