Worked examples

GGL(G)L(G) informalL(G)L(G) formalL(G) regularTipo
G1: Σ→S\Sigma \to S

S→STS \to ST

S→TS \to T

T→(S)T \to (S)

S→(S)S \to (S)

T→()T \to ()		{(),(()),()(),(()()),(())()...}\{(),(()),()(),\\(()()),(())()...\}{[(n)n]m∣n>1,m>1}\{[(^n)^n]^m|n>1,m>1\}[[()]+]+
PCRE

\((?:[^)(]+|(?R))*+\)		Tipo 2.
G2: Σ→A\Sigma \to A

A→1AA \to 1A

A→0BA \to 0B

B→0BB \to 0B

B→0B \to 0		{00,000,0000,...,100,1100,...}\{00,000,0000,...,100,\\1100,...\}{1m0n∣n≥2,m≥0}\{1^m0^n |n\ge2,m\ge0 \}Tipo 3. Lineal derecha.
G3: Σ→λ\Sigma \to \lambda

Σ→S\Sigma \to S

S→SSS \to SS

S→cS \to c		{λ,c,cc,ccc,cccc,...}\{\lambda, c,cc,ccc,cccc,...\}{cn∣n≥0}\{c^n | n \ge 0 \}c*Tipo 2.
G4: Σ→λ\Sigma \to \lambda

Σ→S\Sigma \to S

S→cSdS \to cSd

S→cdS \to cd		{λ,cd,ccdd,cccddd,ccccdddd,...}\{\lambda, cd,ccdd,cccddd,\\ccccdddd,...\}{cndn∣n≥0}\{c^nd^n | n \ge 0 \}(cd)*Tipo 2.
G5: Σ→λ\Sigma \to \lambda

Σ→S\Sigma \to S

S→SdS \to Sd

S→cSS \to cS

S→cS \to c

S→dS \to d

{λ,c,cc,ccc,...,d,dd,cd,cdd,cddd,...,ccd,cccd}\{\lambda, c,cc,ccc,...,d,dd,\\ cd,cdd,cddd,...,ccd,\\cccd\}{cndm∣n≥0,m≥0}\{c^nd^m | n \ge 0,m \ge 0 \}c*d*Tipo 2.
G1, w=()()
G2, w=1100
G3,w=cccc
G4,w=ccdd
G5,w=ccdd

2.a L(G1)=10∗L(G1)=10^*

G1:Σ→BB→B0∣1G1:\Sigma\to B\\ B\to B0|1

2.b L(G2)=10∗L(G2)=10^*

G2:Σ→1B∣1B→0B∣0G2:\Sigma\to 1B|1\\ B\to0B|0

2.c L(G3)=ab∗∪c∗L(G3)=ab^*\cup c^*

G3:Σ→aB∣CB→bB∣λC→cC∣λG3:\Sigma\to aB|C\\ B\to bB|\lambda\\ C\to cC | \lambda

  1. a

L(Ga)={0m1n∣m%2=0,n≥0}L(G_a)=\{0^m1^n|m\%2=0,n\ge0\}

Ga:Σ→ABB→1B∣λA→A00∣λG_a:\Sigma\to AB\\ B\to 1B|\lambda\\ A\to A00 | \lambda
  1. b

L(Gb)={0m1n∣n%2≠0,m≥0}L(G_b)=\{0^m1^n|n\%2\neq0,m\ge0\}

Gb:Σ→ABA→A0∣λB→11B∣1G_b:\Sigma\to AB\\ A\to A0|\lambda\\ B\to11B|1

3.c

L(Gc)={0m1n∣m%2=0,n%2≠0}L(G_c)=\{0^m1^n|m\%2=0,n\%2\neq0\}

Gc:Σ→ABA→A00∣λB→11B∣1G_c:\Sigma\to AB\\ A\to A00 |\lambda\\ B\to11B|1

3.d

L(Gd)=(1∗(00)∗1∗)∗L(G_d)=(1^*(00)^*1^*)^*

Gd:Σ→AA→1A∣ABA∣λB→00ΣG_d:\Sigma\to A\\ A\to 1A|A BA|\lambda\\ B\to 00\Sigma

3.e

L(Ge)={aibj∣i<j}L(G_e)=\{a^ib^j|i<j\}

Ge:Σ→aΣb∣Σb∣bG_e:\Sigma \to a\Sigma b|\Sigma b|b

3.f

L(Gf)={aibj∣i<2j}L(G_f)=\{a^ib^j|i<2j\}

Gf:Σ→Σb∣ab∣Σb∣aΣb∣aaΣbG_f:\Sigma \to \Sigma b|ab|\Sigma b|a\Sigma b|aa\Sigma b

3.g

L(Gg)={aibj∣i>2j}={aibj∣i≥1,⌈i2⌉−1≥j≥0}L(G_g)=\{a^ib^j|i>2j\}=\{a^ib^j|i\ge1,\lceil \dfrac{i}{2} \rceil-1\ge j\ge0\}

Gg:Σ→a∣aΣ∣aaΣbG_g:\Sigma \to a|a\Sigma|aa\Sigma b

3.h

L(Gh)={aibj∣i≠2j}=L(Gf)∪L(Gg)L(G_h)=\{a^ib^j|i\neq2j\}=L(G_f)\cup L(G_g)

Gh:Σ→Σf∣ΣgG_h:\Sigma \to \Sigma_f|\Sigma_g

3.i

L(Gi)={0m1n∣m>n≥0}L(G_i)=\{0^m1^n|m>n\ge0\}

Gi:Σ→0∣0Σ∣0Σ1G_i:\Sigma\to0 |0\Sigma|0\Sigma1

3.j

L(Gj)={0m1n0k∣k=m+n}L(G_j)=\{0^m1^n0^k|k=m+n\}

k=m,n=1k=m,n=1

G:Σ→0Σ0∣1Σ→λG:\Sigma\to0\Sigma0|1\\ \Sigma\to \lambda

k=n,m=1k=n,m=1

G:Σ→0AΣ→λA→1A0∣λG:\Sigma\to0A\\ \Sigma\to \lambda\\ A\to 1A0|\lambda

k=n+mk=n+m

Gj:Σ→0Σ0∣λ∣AA→1A0∣λG_j:\Sigma \to 0\Sigma0|\lambda |A \\ A\to 1A0|\lambda

3.k

L(Gk)={0m1n0k∣n=m+k}L(G_k)=\{0^m1^n0^k|n=m+k\}

n=m,k=1n=m,k=1

G:Σ→A0∣λA→0A1∣λG:\Sigma\to A0|\lambda\\ A\to 0A1|\lambda

n=k,k=1n=k,k=1

G:Σ→0B∣λB→1B0∣λG:\Sigma\to 0B|\lambda\\ B\to 1B0|\lambda

n=m+kn=m+k

Gk:Σ→ABA→0A1∣λB→1B0∣λG_k:\Sigma \to AB \\ A\to 0A1|\lambda\\ B\to 1B0|\lambda

3.l

L(Gl)={wcwR∣w∈{0,1}∗}L(G_l)=\{wcw^R|w\in\{0,1\}^*\}

∣w∣=0|w|=0

G:Σ→cG:\Sigma\to c

w∈{0,1}∗w\in\{0,1\}^*, cc

G:Σ→0Σ0∣1Σ1∣cG:\Sigma\to 0\Sigma 0|1\Sigma 1|c

3.m

L(Gm)={w:na(w)=nb(w)}L(G_m)=\{w:n_a(w)=n_b(w)\}

If w=a,na(w)=1w=a, n_a(w)=1

...

If w=an,na(w)=nw=a^n, n_a(w)=n

If w=b,nb(w)=1w=b, n_b(w)=1

...

If w=bn,nb(w)=nw=b^n, n_b(w)=n

L(Gm)={λ,ab,aabb,aaabbb,...,ba,bbaa,bbbaaa,...,abab,ababba,baab,...}L(G_m)=\{\lambda,ab,aabb,aaabbb,...,ba,bbaa,bbbaaa,...,abab,ababba,baab,...\}

Gm:Σ→ΣΣΣ→aΣbΣ→bΣaΣ→λG_m:\Sigma \to \Sigma \Sigma \\ \Sigma \to a\Sigma b \\ \Sigma \to b \Sigma a\\ \Sigma \to \lambda
  1. L1={anbm:n≥0,m>n}L_1=\{a^nb^m: n\ge 0, m>n\}

ana^n is free, so a rule is A→aA∣λA\to aA|\lambda

m>nm>n, at least L has a bb B→aBb∣Bb∣bB\to aBb|Bb|b

G1:Σ→aΣb∣BB→Bb∣bG_1: \Sigma \to a\Sigma b|B\\ B \to Bb |b
  1. L2={anb2n:n≥0}L_2=\{a^nb^{2n}:n\ge0\}

ana^n, A→aA∣λA\to aA|\lambda

b2nb^{2n}, B→Bbb∣λB\to Bbb|\lambda

G2:Σ→aΣbb∣λG_2: \Sigma \to a\Sigma bb|\lambda

6. L3={an+2bn:n≥1}L_3=\{a^{n+2}b^n: n\ge1\}

an+2a^{n+2}, A→aA∣aaaA\to aA|aaa

bnb^{n}, B→bB∣bB\to bB|b

G3:Σ→aΣb∣aaabG_3: \Sigma \to a\Sigma b|aaab
  1. L4={anbn−1:n≥3}L_4=\{a^nb^{n-1}:n\ge3\}

ana^{n}, A→aA∣aaaA\to aA|aaa

bn−1b^{n-1}, B→Bb∣bbB\to Bb|bb

G4:Σ→aΣb∣aaabbG_4: \Sigma \to a\Sigma b|aaabb
  1. L1L2L_1L_2
    G5=Σ→AXA→aAb∣BB→Bb∣bX→aXbb∣λG_5=\Sigma\to AX\\ A \to aA b|B\\ B \to Bb |b\\ X \to aX bb|\lambda

9.L1∪L2L_1\cup L_2

G6=Σ→A∣XA→aAb∣BB→Bb∣bX→aXbb∣λG_6=\Sigma\to A|X\\ A \to aA b|B\\ B \to Bb |b\\ X \to aX bb|\lambda
  1. L13L^3_1

L1={anbm:n≥0,m>n}L_1=\{a^nb^m: n\ge 0, m>n\}