---
date: '2025-04-22'
description: formal grammar defined as 4-tuple with non-terminals, terminals, production rules, and start symbol, recognized by pushdown automata.
id: Context-Free Grammar
modified: 2026-06-05 15:08:28 GMT-04:00
tags:
  - math/discrete
title: Context-Free Grammar
created: '2025-04-22'
published: '2025-04-22'
pageLayout: default
slug: thoughts/Context-Free-Grammar
permalink: https://aarnphm.xyz/thoughts/Context-Free-Grammar.md
generator:
  quartz: v4.6.0
  hostedProvider: Cloudflare
  baseUrl: aarnphm.xyz
full: https://aarnphm.xyz/llms-full.txt
---
> \[!abstract\] Abstract
>
> 4-tuple $(N, \Sigma, P, S)$
>
> - $N$: A finite set of non-terminal
> - $\Sigma$: A finite set of terminal $N \cap \Sigma = \emptyset$
> - $P$: is a finite subset of $N \times (N \cup \Sigma)^{*}$
> - $S$: $S \in N$, the start symbols

## Pushdown Automata

> \[!abstract\] Abstract
>
> $M = (Q, \Sigma, \Gamma, \delta, s, \perp, F)$