لم اوگدن

در تئوری زبان‌های فرمال (زبان‌های صوری)، لم اوگدن (نامگذاری شده بعد از William F.Ogden) انعطاف‌پذیری بیشتری به لم پمپاژ برای زبان‌های مستقل از متن می‌دهد.

لم اوگدن اظهار می‌کند، اگر زبان L مستقل از متن باشد، آنگاه عدد p>0 وجود دارد بطوریکه برای هر رشته w به طول حداقل p در زبان L، برای هر انتخاب p تایی یا بیشتر از نمادهای w
رشته wرا می‌توان به صورت w=uxyzv تجزیه کرد، بطوریکه

 رشته xz جلوی حداقل یک نماد مشخص شده باشد.
 رشته xyz حاوی حداکثر p نماد باشد.
 برای i ≥ ۰ رشتهٔ uxiyziv عضو زبان L باشد.

زمانی که لم پمپاژ برای زبان‌های مستقل از متن کارآمد نیست، لم Ogden می‌تواند نشان دهد که یک زبان مستقل از متن نیست.
برای مثال زبان {a i b j c k d l: i = 0 or j = k = l}.

مشاهده می‌شود زمانیکه تمام نمادهای w  انتخاب می‌شود لم پمپاژ با لم اوگدن برابر است. به بیان دیگر لم پمپاژ حالت خاصی از لم اوگدن است.

همچنین این لم می‌تواند ثابت کند که بعضی از زبان‌ها ذاتاً مبهم هستند.

جستارهای وابسته

منابع 

زبان‌های صوری
لم‌ها
ویکی‌سازی رباتیک