The listed programs were used to generate all valid Icelandic kennitala, then create a DFA that recognizes them. It was huge, containing 13.6 million states. This DFA was then minimized with this program. Surprisingly, you only need 132 states to match Icelandic kennitala!

The states program was then used to generate this regex (warning: large file) for matching Icelandic kennitala. Unfortunately it's huge.

Finding the smallest regular expression that matches a given regular language (even a finite one) is an NP-Complete problem, and explains the huge blowup in size after running the State Elimination Method, which states implements. However, the order in which states are eliminated plays a big role in how large this blowup is. Using Simulated Annealing to find an elimination order that minimizes this blowup, a 14,791 byte regex for Icelandic kennitala was discovered:

((2902((483|522|564|248|849|603|044|768|(20|08|72)6|329|645|125|(80|68|16)7)(88|96|29|02|45|61|53|10|37)|(487|884|526|568|445|842|607|965|048|3(64|22)|(40|28|92)3|649|129)(28|36|79|52|95|01|60|44|87)|(887|529|244|448|845|968|764|(20|08|72)2|3(67|25)|(40|28|92)6|(80|68|16)3)(38|46|89|62|11|03|70|54|97)|(485|882|524|566|443|605|963|046|(20|08|72)8|362|647|127|(80|68|16)9)(58|66|82|15|31|23|90|74|07)|(488|885|527|569|242|446|843|608|966|049|762|3(65|23)|(40|28|92)4)(68|76|09|92|25|41|33|84|17)|(889|562|246|847|042|766|(20|08|72)4|3(69|27)|(40|28|92)8|643|123|(80|68|16)5)(08|16|59|32|75|91|83|40|24|67)|(484|523|565|249|442|604|962|045|769|(20|08|72)7|646|126|(80|68|16)8)(18|26|69|42|85|93|50|34|77)|(888|245|449|846|969|765|(20|08|72)3|3(68|26)|(40|28|92)7|642|122|(80|68|16)4)(78|86|19|35|51|43|00|94|27)|(486|883|525|567|444|606|964|047|(20|08|72)9|363|(40|28|92)2|648|128)(98|39|12|55|71|63|20|04|47)|(482|563|247|848|602|043|767|(20|08|72)5|328|(40|28|92)9|644|124|(80|68|16)6)(48|56|99|72|05|21|13|80|64)|(489|886|528|243|447|844|609|967|763|3(66|24)|(40|28|92)5|(80|68|16)2)(06|49|22|65|81|73|30|14|57))|(290(96|41|19|74|63|30|85|52)|(19|05|22)(116|105|127|0(46|79|24|13|90|35|68|57))|(13|27)0(66|11|99|44|33|55|22|88|77)|31(129|107|0(81|59|70|15|37))|(17|03|20)(119|108|0(16|71|49|93|60|82|38|27))|(301|(13|27)1)(14|03|25)|(16|02)(126|104|115|0(56|89|34|23|45|12|78|67))|(06|23)(109|120|0(61|39|94|83|50|72|28|17))|(18|04|21)(101|123|112|0(86|31|64|53|20|75|42|97))|(15|01)0(96|41|19|74|63|30|85|52)|(12|09|26)(121|110|0(51|29|84|73|40|95|62|18))|(291|(15|01)1)(11|00|22)|(10|07|24)(124|113|102|0(76|21|54|43|10|65|32|98|87))|(11|08|25)(106|128|117|0(36|91|69|14|80|25|58|47))|300(66|11|99|44|33|55|88|77)|(14|28)(129|118|107|0(26|81|59|70|15|92|48|37)))((63|42|84|58|79|16|37)(88|96|29|02|45|61|53|10|37)|(67|46|04|88|25|72|93)(28|36|79|52|95|01|60|44|87)|(49|07|54|28|75|12|96|33)(38|46|89|62|11|03|70|54|97)|(65|44|02|86|23|18|39)(58|66|82|15|31|23|90|74|07)|(68|47|05|89|52|26|73|94)(68|76|09|92|25|41|33|84|17)|(09|82|56|77|14|98|35)(08|16|59|32|75|91|83|40|24|67)|(64|43|85|59|22|17|38)(18|26|69|42|85|93|50|34|77)|(08|55|29|76|13|97|34)(78|86|19|35|51|43|00|94|27)|(66|45|03|87|24|19|92)(98|39|12|55|71|63|20|04|47)|(62|83|57|78|15|99|36)(48|56|99|72|05|21|13|80|64)|(69|48|06|53|27|74|95|32)(06|49|22|65|81|73|30|14|57))|(290(98|43|10|76|65|32|87|54)|(19|05|22)(118|107|129|0(48|70|26|81|15|92|37|59))|(13|27)0(68|13|90|46|35|57|24|79)|31(120|109|0(83|50|72|17|39))|(17|03|20)(110|121|0(18|73|40|51|95|62|84|29))|(301|(13|27)1)(16|05|27)|(16|02)(128|106|117|0(58|80|36|91|25|47|14|69))|(06|23)(100|111|122|0(63|30|96|41|85|52|74|19))|(18|04|21)(103|125|114|0(88|33|66|11|55|22|77|44|99))|(15|01)0(98|43|10|76|21|65|32|87|54)|(12|09|26)(123|101|112|0(53|20|86|31|75|42|97|64))|(291|(15|01)1)(13|02|24)|(10|07|24)(126|115|104|0(78|23|56|45|12|67|34|89))|(11|08|25)(108|119|0(38|93|60|16|71|82|27|49))|300(68|13|90|46|35|57|79)|(14|28)(120|109|0(28|83|50|61|72|17|94|39)))((93|72|04|88|46|25|67)(88|96|29|02|45|61|53|10|37)|(97|76|34|08|55|13|29)(28|36|79|52|95|01|60|44|87)|(79|37|84|58|42|16|63)(38|46|89|62|11|03|70|54|97)|(95|74|32|06|53|48|27|69)(58|66|82|15|31|23|90|74|07)|(98|77|35|09|82|56|14)(68|76|09|92|25|41|33|84|17)|(39|02|86|44|18|23|65)(08|16|59|32|75|91|83|40|24|67)|(94|73|05|89|52|47|26|68)(18|26|69|42|85|93|50|34|77)|(38|85|59|43|17|22|64)(78|86|19|35|51|43|00|94|27)|(96|75|33|07|54|49|12|28)(98|39|12|55|71|63|20|04|47)|(92|03|87|45|19|24|66)(48|56|99|72|05|21|13|80|64)|(99|78|36|83|57|15|62)(06|49|22|65|81|73|30|14|57))|(290(95|40|18|73|62|84|51)|(19|05|22)(115|104|126|0(45|78|23|89|12|34|67|56))|(13|27)0(65|10|98|43|32|54|21|87|76)|31(128|106|0(80|58|14|36))|(17|03|20)(118|129|107|0(15|70|48|59|92|81|37|26))|(301|(13|27)1)(13|02|24)|(16|02)(125|103|114|0(55|88|33|99|22|44|11|77|66))|(06|23)(108|119|0(60|38|93|49|82|71|27|16))|(18|04|21)(100|122|111|0(85|30|63|19|52|74|41|96))|(15|01)0(95|40|18|73|29|62|84|51)|(12|09|26)(120|109|0(50|28|83|39|72|94|61|17))|(291|(15|01)1)(10|21)|(10|07|24)(123|112|101|0(75|20|53|42|64|31|97|86))|(11|08|25)(105|127|116|0(35|90|68|13|79|24|57|46))|300(65|10|98|43|32|54|87|76)|(14|28)(128|117|106|0(25|80|58|69|14|91|47|36)))((82|14|98|09|56|35|77)(88|96|29|02|45|61|53|10|37)|(86|44|18|65|02|23|39)(28|36|79|52|95|01|60|44|87)|(89|47|94|68|05|52|26|73)(38|46|89|62|11|03|70|54|97)|(84|42|16|63|58|37|79)(58|66|82|15|31|23|90|74|07)|(87|45|19|92|66|03|24)(68|76|09|92|25|41|33|84|17)|(49|12|96|07|54|28|33|75)(08|16|59|32|75|91|83|40|24|67)|(83|15|99|62|57|36|78)(18|26|69|42|85|93|50|34|77)|(48|95|69|06|53|27|32|74)(78|86|19|35|51|43|00|94|27)|(85|43|17|64|59|22|38)(98|39|12|55|71|63|20|04|47)|(13|97|08|55|29|34|76)(48|56|99|72|05|21|13|80|64)|(88|46|93|67|04|25|72)(06|49|22|65|81|73|30|14|57))|(290(93|49|16|71|60|38|82)|(19|05|22)(113|102|124|0(43|76|21|87|10|98|32|65|54))|(13|27)0(63|19|96|41|30|52|85|74)|31(126|104|0(89|56|78|12|34))|(17|03|20)(116|127|105|0(13|79|46|57|90|68|35|24))|(301|(13|27)1)(11|00|22)|(16|02)(123|101|112|0(53|86|31|97|20|42|75|64))|(06|23)(106|117|128|0(69|36|91|47|80|58|25|14))|(18|04|21)(109|120|0(83|39|61|17|50|28|72|94))|(15|01)0(93|49|16|71|27|60|38|82)|(12|09|26)(129|107|118|0(59|26|81|37|70|48|92|15))|(291|(15|01)1)(19|08)|(10|07|24)(121|110|0(73|29|51|40|18|62|95|84))|(11|08|25)(103|125|114|0(33|99|66|11|77|88|22|55|44))|300(63|19|96|41|30|52|85|74)|(14|28)(126|115|104|0(23|89|56|67|78|12|45|34)))((73|52|94|68|89|26|05|47)(88|96|29|02|45|61|53|10|37)|(77|56|14|98|35|82|09)(28|36|79|52|95|01|60|44|87)|(59|17|64|38|85|22|43)(38|46|89|62|11|03|70|54|97)|(75|54|12|96|33|28|07|49)(58|66|82|15|31|23|90|74|07)|(78|57|15|99|62|36|83)(68|76|09|92|25|41|33|84|17)|(19|92|66|87|24|03|45)(08|16|59|32|75|91|83|40|24|67)|(74|53|95|69|32|27|06|48)(18|26|69|42|85|93|50|34|77)|(18|65|39|86|23|02|44)(78|86|19|35|51|43|00|94|27)|(76|55|13|97|34|29|08)(98|39|12|55|71|63|20|04|47)|(72|93|67|88|25|04|46)(48|56|99|72|05|21|13|80|64)|(79|58|16|63|37|84|42)(06|49|22|65|81|73|30|14|57))|(290(90|46|13|79|68|35|57)|(19|05|22)(110|121|0(40|73|29|84|18|95|62|51))|(13|27)0(60|16|93|49|38|27|82|71)|31(123|101|0(86|53|75|31))|(17|03|20)(113|124|102|0(10|76|43|54|98|65|87|32|21))|(301|(13|27)1)(19|08)|(16|02)(120|109|0(50|83|39|94|28|17|72|61))|(06|23)(103|114|125|0(66|33|99|44|88|55|77|22|11))|(18|04|21)(106|128|117|0(80|36|69|14|58|25|47|91))|(15|01)0(90|46|13|79|24|68|35|57)|(12|09|26)(126|104|115|0(56|23|89|34|78|45|67|12))|(291|(15|01)1)(16|05|27)|(10|07|24)(129|118|107|0(70|26|59|48|15|37|92|81))|(11|08|25)(100|122|111|0(30|96|63|19|74|85|52|41))|300(60|16|93|49|38|82|71)|(14|28)(123|112|101|0(20|86|53|64|75|97|42|31)))((83|62|78|99|36|15|57)(88|96|29|02|45|61|53|10|37)|(87|66|24|45|92|03|19)(28|36|79|52|95|01|60|44|87)|(69|27|74|48|95|32|06|53)(38|46|89|62|11|03|70|54|97)|(85|64|22|43|38|17|59)(58|66|82|15|31|23|90|74|07)|(88|67|25|72|46|93|04)(68|76|09|92|25|41|33|84|17)|(29|76|97|34|08|13|55)(08|16|59|32|75|91|83|40|24|67)|(84|63|79|42|37|16|58)(18|26|69|42|85|93|50|34|77)|(28|75|49|96|33|07|12|54)(78|86|19|35|51|43|00|94|27)|(86|65|23|44|39|02|18)(98|39|12|55|71|63|20|04|47)|(82|77|98|35|09|14|56)(48|56|99|72|05|21|13|80|64)|(89|68|26|73|47|94|05|52)(06|49|22|65|81|73|30|14|57))|(290(97|42|75|64|31|86|53)|(19|05|22)(117|106|128|0(47|25|80|14|91|36|69|58))|(13|27)0(67|12|45|34|56|23|89|78)|31(108|0(82|71|16|38))|(17|03|20)(120|109|0(17|72|50|94|61|83|39|28))|(301|(13|27)1)(15|04|26)|(16|02)(127|105|116|0(57|35|90|24|46|13|79|68))|(06|23)(110|121|0(62|95|40|84|51|73|29|18))|(18|04|21)(102|124|113|0(87|32|65|10|54|21|76|43|98))|(15|01)0(97|42|75|20|64|31|86|53)|(12|09|26)(122|100|111|0(52|85|30|74|41|96|63|19))|(291|(15|01)1)(12|01|23)|(10|07|24)(125|114|103|0(77|22|55|44|11|66|33|99|88))|(11|08|25)(107|129|118|0(37|92|15|70|81|26|59|48))|300(67|12|45|34|56|89|78)|(14|28)(119|108|0(27|82|60|71|16|93|49|38)))((23|02|44|18|39|86|65)(88|96|29|02|45|61|53|10|37)|(27|06|74|48|95|32|53|69)(28|36|79|52|95|01|60|44|87)|(09|77|14|98|35|82|56)(38|46|89|62|11|03|70|54|97)|(25|04|72|46|93|88|67)(58|66|82|15|31|23|90|74|07)|(28|07|75|49|12|96|33|54)(68|76|09|92|25|41|33|84|17)|(79|42|16|37|84|58|63)(08|16|59|32|75|91|83|40|24|67)|(24|03|45|19|92|87|66)(18|26|69|42|85|93|50|34|77)|(78|15|99|36|83|57|62)(78|86|19|35|51|43|00|94|27)|(26|05|73|47|94|89|52|68)(98|39|12|55|71|63|20|04|47)|(22|43|17|38|85|59|64)(48|56|99|72|05|21|13|80|64)|(29|08|76|13|97|34|55)(06|49|22|65|81|73|30|14|57))|(290(92|48|15|70|37|81|59)|(19|05|22)(112|101|123|0(42|75|20|86|97|31|64|53))|(13|27)0(62|18|95|40|51|29|84|73)|31(125|103|0(88|55|77|11|33))|(17|03|20)(115|126|104|0(12|78|45|56|67|89|34|23))|(301|(13|27)1)(10|21)|(16|02)(122|100|111|0(52|85|30|96|41|19|74|63))|(06|23)(105|116|127|0(68|35|90|46|57|79|24|13))|(18|04|21)(108|119|0(82|38|60|16|27|71|49|93))|(15|01)0(92|48|15|70|26|37|81|59)|(12|09|26)(128|106|117|0(58|25|80|36|47|91|69|14))|(291|(15|01)1)(18|07|29)|(10|07|24)(120|109|0(72|28|50|17|61|39|94|83))|(11|08|25)(102|124|113|0(32|98|65|10|76|87|21|54|43))|300(62|18|95|40|51|84|73)|(14|28)(125|114|103|0(22|88|55|66|77|11|99|44|33)))((03|92|24|19|66|45|87)(88|96|29|02|45|61|53|10|37)|(07|96|54|28|75|12|33|49)(28|36|79|52|95|01|60|44|87)|(99|57|78|15|62|36|83)(38|46|89|62|11|03|70|54|97)|(05|94|52|26|73|68|47|89)(58|66|82|15|31|23|90|74|07)|(08|97|55|29|76|13|34)(68|76|09|92|25|41|33|84|17)|(59|22|17|64|38|43|85)(08|16|59|32|75|91|83|40|24|67)|(04|93|25|72|67|46|88)(18|26|69|42|85|93|50|34|77)|(58|79|16|63|37|42|84)(78|86|19|35|51|43|00|94|27)|(06|95|53|27|74|69|32|48)(98|39|12|55|71|63|20|04|47)|(02|23|18|65|39|44|86)(48|56|99|72|05|21|13|80|64)|(09|98|56|77|14|35|82)(06|49|22|65|81|73|30|14|57))|(290(45|12|78|67|34|89|56)|(19|05|22)(109|120|0(72|28|83|17|94|39|61|50))|(13|27)0(15|92|48|37|59|26|81|70)|31(122|100|0(85|52|74|19|30))|(17|03|20)(112|123|101|0(75|42|53|97|64|86|31|20))|(301|(13|27)1)(18|07|29)|(16|02)(108|119|0(82|38|93|27|49|16|71|60))|(06|23)(102|113|124|0(65|32|98|43|87|54|76|21|10))|(18|04|21)(105|127|116|0(35|68|13|57|24|79|46|90))|(15|01)0(45|12|78|23|67|34|89|56)|(12|09|26)(125|103|114|0(55|22|88|33|77|44|99|66|11))|(291|(15|01)1)(15|04|26)|(10|07|24)(128|117|106|0(25|58|47|14|69|36|91|80))|(11|08|25)(121|110|0(95|62|18|73|84|29|51|40))|300(15|92|48|37|59|81|70)|(14|28)(122|111|100|0(85|52|63|74|19|96|41|30)))((13|34|08|29|76|55|97)(88|96|29|02|45|61|53|10|37)|(17|64|38|85|22|43|59)(28|36|79|52|95|01|60|44|87)|(67|04|88|25|72|46|93)(38|46|89|62|11|03|70|54|97)|(15|62|36|83|78|57|99)(58|66|82|15|31|23|90|74|07)|(18|65|39|02|86|23|44)(68|76|09|92|25|41|33|84|17)|(69|32|06|27|74|48|53|95)(08|16|59|32|75|91|83|40|24|67)|(14|35|09|82|77|56|98)(18|26|69|42|85|93|50|34|77)|(68|05|89|26|73|47|52|94)(78|86|19|35|51|43|00|94|27)|(16|63|37|84|79|42|58)(98|39|12|55|71|63|20|04|47)|(12|33|07|28|75|49|54|96)(48|56|99|72|05|21|13|80|64)|(19|66|03|87|24|45|92)(06|49|22|65|81|73|30|14|57))|(290(91|47|14|69|36|80|58)|(19|05|22)(111|100|122|0(41|74|85|19|96|30|63|52))|(13|27)0(61|17|94|39|50|28|83|72)|31(124|102|0(87|54|76|10|32))|(17|03|20)(114|125|103|0(11|77|44|55|99|66|88|33|22))|(301|(13|27)1)(09|20)|(16|02)(121|110|0(51|84|95|29|40|18|73|62))|(06|23)(104|115|126|0(67|34|45|89|56|78|23|12))|(18|04|21)(107|129|118|0(81|37|15|59|26|70|48|92))|(15|01)0(91|47|14|25|69|36|80|58)|(12|09|26)(127|105|116|0(57|24|35|79|46|90|68|13))|(291|(15|01)1)(17|06|28)|(10|07|24)(119|108|0(71|27|49|16|60|38|93|82))|(11|08|25)(101|123|112|0(31|97|64|75|86|20|53|42))|300(61|17|94|39|50|83|72)|(14|28)(124|113|102|0(21|87|54|65|76|10|98|43|32)))((43|22|64|38|59|85|17)(88|96|29|02|45|61|53|10|37)|(47|26|94|68|05|52|73|89)(28|36|79|52|95|01|60|44|87)|(29|97|34|08|55|76|13)(38|46|89|62|11|03|70|54|97)|(45|24|92|66|03|87|19)(58|66|82|15|31|23|90|74|07)|(48|27|95|69|32|06|53|74)(68|76|09|92|25|41|33|84|17)|(99|62|36|57|78|83|15)(08|16|59|32|75|91|83|40|24|67)|(44|23|65|39|02|86|18)(18|26|69|42|85|93|50|34|77)|(98|35|09|56|77|82|14)(78|86|19|35|51|43|00|94|27)|(46|25|93|67|04|72|88)(98|39|12|55|71|63|20|04|47)|(42|63|37|58|79|84|16)(48|56|99|72|05|21|13|80|64)|(49|28|96|33|07|54|75|12)(06|49|22|65|81|73|30|14|57))|(290(99|44|11|77|66|33|88|55)|(19|05|22)(119|108|0(49|71|27|82|16|93|38|60))|(13|27)0(69|14|91|47|36|58|25|80)|31(121|0(84|51|73|18))|(17|03|20)(111|122|100|0(19|74|41|52|96|63|85|30))|(301|(13|27)1)(17|06|28)|(16|02)(129|107|118|0(59|81|37|92|26|48|15|70))|(06|23)(101|112|123|0(64|31|97|42|86|53|75|20))|(18|04|21)(104|126|115|0(89|34|67|12|56|23|78|45))|(15|01)0(99|44|11|77|22|66|33|88|55)|(12|09|26)(124|102|113|0(54|21|87|32|76|43|98|65|10))|(291|(15|01)1)(14|03|25)|(10|07|24)(127|116|105|0(79|24|57|46|13|68|35|90))|(11|08|25)(109|120|0(39|94|61|17|72|83|28|50))|300(69|14|91|47|36|58|80)|(14|28)(121|110|0(29|84|51|62|73|18|95|40)))((53|32|74|48|69|06|95|27)(88|96|29|02|45|61|53|10|37)|(57|36|78|15|62|83|99)(28|36|79|52|95|01|60|44|87)|(39|44|18|65|02|86|23)(38|46|89|62|11|03|70|54|97)|(55|34|76|13|08|97|29)(58|66|82|15|31|23|90|74|07)|(58|37|79|42|16|63|84)(68|76|09|92|25|41|33|84|17)|(72|46|67|04|88|93|25)(08|16|59|32|75|91|83|40|24|67)|(54|33|75|49|12|07|96|28)(18|26|69|42|85|93|50|34|77)|(45|19|66|03|87|92|24)(78|86|19|35|51|43|00|94|27)|(56|35|77|14|09|82|98)(98|39|12|55|71|63|20|04|47)|(52|73|47|68|05|89|94|26)(48|56|99|72|05|21|13|80|64)|(59|38|43|17|64|85|22)(06|49|22|65|81|73|30|14|57))|(290(94|17|72|61|39|83|50)|(19|05|22)(114|103|125|0(44|77|22|88|11|99|33|66|55))|(13|27)0(64|97|42|31|53|20|86|75)|31(127|105|0(57|79|13|35))|(17|03|20)(117|128|106|0(14|47|58|91|69|80|36|25))|(301|(13|27)1)(12|01|23)|(16|02)(124|102|113|0(54|87|32|98|21|43|10|76|65))|(06|23)(107|118|129|0(37|92|48|81|59|70|26|15))|(18|04|21)(121|110|0(84|62|18|51|29|73|40|95))|(15|01)0(94|17|72|28|61|39|83|50)|(12|09|26)(108|119|0(27|82|38|71|49|93|60|16))|(291|(15|01)1)(09|20)|(10|07|24)(122|111|100|0(74|52|41|19|63|30|96|85))|(11|08|25)(104|126|115|0(34|67|12|78|89|23|56|45))|300(64|97|42|31|53|86|75)|(14|28)(127|116|105|0(24|57|68|79|13|90|46|35)))((33|12|54|28|49|96|75|07)(88|96|29|02|45|61|53|10|37)|(37|16|84|58|42|63|79)(28|36|79|52|95|01|60|44|87)|(19|87|24|45|92|66|03)(38|46|89|62|11|03|70|54|97)|(35|14|82|56|98|77|09)(58|66|82|15|31|23|90|74|07)|(38|17|85|59|22|43|64)(68|76|09|92|25|41|33|84|17)|(89|52|26|47|94|68|73|05)(08|16|59|32|75|91|83|40|24|67)|(34|13|55|29|97|76|08)(18|26|69|42|85|93|50|34|77)|(88|25|46|93|67|72|04)(78|86|19|35|51|43|00|94|27)|(36|15|83|57|99|62|78)(98|39|12|55|71|63|20|04|47)|(32|53|27|48|95|69|74|06)(48|56|99|72|05|21|13|80|64)|(39|18|86|23|44|65|02)(06|49|22|65|81|73|30|14|57)))[089]|290200(8(49|22|81|14|73|65|30|57|06)|7(09|92|41|84|33|25|68|17|76)|2(29|02|61|53|45|10|88|37|96)|3(69|42|34|93|85|50|18|77|26)|9(89|62|11|54|03|70|38|97|46)|6(79|52|01|44|95|60|28|87|36)|4(82|31|74|23|15|90|58|07|66)|5(39|12|71|04|63|55|20|98|47))0)

Note: This regex matches valid kennitala of individuals born between 1800 and 2099. See this article for a classification of valid kennitala.