Llenguatge regular: diferència entre les revisions

Per trobar la posició dels llenguatges regulars dins de la [[jerarquia de Chomsky]] cal notar que tot llenguatge regular és [[Gramàtica lliure de context|lliure del context]]. A l'inrevés no és cert: per exemple el llenguatge consistent en totes les cadenes que tenen el mateix nombre d'''a''s i de ''b''s és lliure del context però no és regular. Per provar que un llenguatge d'aquest tipus no és regular es fa servir el [[teorema de Myhill-Nerode]] o el [[Lema de bombeigbombament per a llenguatges regulars|Lema de bombeigbombament]].<ref>{{Ref-web|url=https://cs.stackexchange.com/questions/1031/how-to-prove-that-a-language-is-not-regular|títol=How to prove that a language is not regular?|consulta=2019-02-13}}</ref>