grammar - One Language and Proof How it's ambiguous? -


i took midterm couldn't answer question.

how can show following language ambiguous ?

l={a n bm c p : n≠m} u {a n bm c p : m≠p}

i think hard, can me automated tools or ... how can prove ?

consider 1 possible grammar language {anbmcp : n≠m}:

s → x c | x b c x → ε | x b → | a b → b | b b c → ε | c c

in grammar, left-most derivation of word not expand , c until other non-terminals have been expanded. similar grammar other half of union (anbmcp : m≠p} expand as before other non-terminal expanded. word in intersection of 2 subsets therefore have (at least) 2 distinct derivations.

proving language inherently ambiguous requires proving above true grammar language. such proof based on ogden's lemma, generalization of pumping lemma context free languages; proof consists of demonstrating word can "pumped" in 2 different ways.

it relatively easy find proof similar language {anbmcp : n=m} ∪ {anbmcp : m=p} inherently ambiguous: it's used example in textbooks on formal language theory. think proof language "more difficult" in requires consideration of more cases, should similar.

an alternative approach analytic method of flajolet.


-

Comments

Post a Comment

Popular posts from this blog

css - SVG using textPath a symbol not rendering in Firefox -

using textpath within symbol doesn't render in firefox. renders fine in latest chrome , ie, when try reference symbol, svg text doesn't render in firefox (37.0.1) - first box appears empty. code below (no external dependencies), there should 2 boxes word test flowing vertically in centre of each. edit: thought issue somehow involved flexbox layout, until paul pointed out issue exists without flexbox layout. the html is: <div> <svg id="not_working" viewbox="0 0 250 1200" preserveaspectratio="xmidymid meet"> <symbol id="test_symbol1" preserveaspectratio="xmidymid meet" viewbox="0 0 250 1200"> <path id="test_symbol_path" d="m 100 1200 l 100 0" /> <text font-size="100" fill="red"> <textpath text-anchor="middle" startoffset="50%" xlink:href="#test_symbol_path...
Read more

Java 8 + Maven Javadoc plugin: Error fetching URL -

i attempting generate javadoc links javadoc dependencies. have tried various means generate javadoc not produce qualified class names references classes dependencies. wanted links java doc simplified class names. however, java api classnames, no links , have qualified class names. working java 8. have following configuration: <plugin> <groupid>org.apache.maven.plugins</groupid> <artifactid>maven-javadoc-plugin</artifactid> <version>2.10.2</version> <configuration> <reportoutputdirectory>${project.basedir}/target</reportoutputdirectory> <destdir>javadoc</destdir> <windowtitle>epiphany</windowtitle> <doctitle>epiphany</doctitle> <show>private</show> <detectlinks>false</detectlinks> <detectoffline...
Read more

order - Notification for user in user account opencart -

thanks helps or points me in right direction. i want show pending notification user in account page after login. notification show when order status pending. after changing other status admin remove notification. this notification show like: your order id: order status: , [ button custom url] if multiple order show multiple order id. open cart version 1.5.6.3 custom theme. $this->load->model('account/order'); $results = $this->model_account_order->getorders(); foreach ($results $result) { $product_total = $this->model_account_order->gettotalorderproductsbyorderid($result['order_id']); $voucher_total = $this->model_account_order->gettotalordervouchersbyorderid($result['order_id']); if( $result['status'] =! 5){ // 5 order status means completed $this->data['orders'][] = array( 'order_id' => $result['order_id'], ...
Read more