syntax - What is a regular language? -



syntax - What is a regular language? -

i'm trying understand concept of languages levels (regular, context free, context sensitive, etc..).

i can easily, explanations find load of symbols , talk 'sets'. have 2 questions:

can describe in words regular language , how languages @ different languages differ?

where people larn understand stuff? understand it, formal mathematics? had couple of courses @ uni used , barely understood tutors assumed knew it. can larn , why people 'expected' know in many sources? it's there's gap in education.

here's example:

any language belonging set regular language on alphabet.

how can language 'over' anything?

in context of computer science, word concatenation of symbols. used symbols called alphabet. example, words formed out of alphabet {0,1,2,3,4,5,6,7,8,9} 1, 2, 12, 543, 1000, , 002.

a language subset of possible words. example, might want define language captures elite mi6 agents. start double-0, words in language 007, 001, 005, , 0012, not 07 or 15. simplicity's sake, language "over alphabet" instead of "a subset of words formed concatenation of symbols in alphabet".

in computer science, want classify languages. phone call language regular if can decided if word in language algorithm/a machine constant (finite) memory examining symbols in word 1 after another. language consisting of word 42 regular, can decide whether word in without requiring arbitrary amounts of memory; check whether first symbol 4, whether sec 2, , whether more numbers follow.

all languages finite number of words regular, because can (in theory) build command flow tree of constant size (you can visualize bunch of nested if-statements examine 1 digit after other). example, can test whether word in "prime numbers between 10 , 99" language next construct, requiring no memory except 1 encode @ code line we're at:

if word[0] == 1: if word[1] == 1: # 11 homecoming true # "accept" word, i.e. it's in language if word[1] == 3: # 13 homecoming true ... homecoming false

note finite languages regular, not regular languages finite; our double-0 language contains infinite number of words (007, 008, 004242 , 0012345), can tested constant memory: test whether word belongs in it, check whether first symbol 0, , whether sec symbol 0. if that's case, take it. if word shorter two, or not start 00, it's not mi6 code name.

formally, build of finite-state machine or regular grammar used prove language regular. these similar if-statements above, allow arbitrarily long words. if there's finite-state machine, there regular grammar, , vice versa, it's sufficient show either. example, finite state machine our double-0 language is:

start state: if input = 0 goto state 2 start state: if input = 1 fail start state: if input = 2 fail ... state 2: if input = 0 take state 2: if input != 0 fail accept: input, take

the equivalent regular grammar is:

start → 0 b b → 0 take accept → 0 take accept → 1 take ...

the equivalent regular expression is:

00[0-9]*

some languages not regular. example, language of number of 1, followed same number of 2 (often written 1n2n, arbitrary n) not regular - need more constant amount of memory(= constant number of states) store number of 1s decide whether or not word in language.

this should explained in theoretical computer science course. luckily, wikipedia explains both formal , regular languages quite nicely.

syntax programming-languages bnf regular-language formal-languages

Comments

Post a Comment

Popular posts from this blog

iphone - Dismissing a UIAlertView -

iphone - Dismissing a UIAlertView - i set in app purchase app, , when user taps button, purchase started. basically, tap button, , depending on speed on net connection, waiting 10 seconds until new alert view comes asking if purchase product. user tap button multiple times since nil came up, , multiple purchase alert views come up. additionally, maybe seen user app bug. in end, problem. i want alert view come spinning wheel says "loading..." when users taps purchase button. problem is, how dismiss when new alert view comes asking user if want purchase product? if ([uialertview alloc] says: @"whatever apple's alert view says") { //dismiss "loading..." alert view here } i uncertainty work, input appreciated. thanks! you need have access alertview. can this. create alertview instance var in app delegate , when want show loading initialize instance var assign property , when want dismiss phone call [alertviewinstance d...
Read more

intellij idea - Update external libraries with intelij and java -

intellij idea - Update external libraries with intelij and java - simple plenty really. i'm using apache jars, i'll create changes jar's every often. these jars listed external libs in intelij (i.e classpath looking install dir of jar's). when create changes intelij doesn't seem know new implementation. have remove jar external library , re-ad it. does know have intelij picks changes automatically ? i've done clean , rebuild project had little effect. you can go preferences -> build, execution, deployment -> build tools -> maven -> importing , check box says import maven projects automatically . in mac, can command + shift + a , come in action reimport , click on reimport maven projects . intellij-idea
Read more

javascript - send data from a new window to previous window in php -

javascript - send data from a new window to previous window in php - i have image in main.php file : <img src="..\images\image.gif" class="cur" onclick="imgwin();"> when click on image below function has called : function imgwin() { imagewin=window.open("../pages/img.php","imagewin","toolbar=no,width=500,height=200,directories=no,menubar=no,scrollbars=yes"); } this function opens img.php in new window img.php file : <html> <head> <title>upload image</title> </head> <body> <form name="imgform" method="get" action="#"> address : <input type="file" name="imgurl" size="50"> description : <input type="text" name="description" size="50"> <input type="submit" value="sumbit...
Read more