StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
15578641
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
6
CommunityOwnedDate
CreationDate
2013-03-22T19:44:09.357
FavoriteCount
0
LastActivityDate
2013-03-25T21:22:41.703
LastEditDate
2017-05-23T11:54:57.007
LastEditorUserId
-1
OwnerUserId
1673391
ParentId
15559324
PostTypeId
2
Score
7
ViewCount
0
LastEditorDisplayName
text
Body
<h2>How to write grammar for formal language?</h2> Before read my this answer you should read first: <a href="https://stackoverflow.com/questions/15126824/tips-for-creating-context-free-grammar/15130451#15130451">Tips for creating Context free grammars</a>. <h2>Grammar for {an bm | n,m = 0,1,2,..., n <= 2m }</h2> <blockquote> What is you language L = {an bm | n,m = 0,1,2,..., n <= 2m } description? </blockquote> Language description: The language L is consist of set of all strings in which symbols <code>a</code> followed by symbols <code>b</code>, where number of symbol <code>b</code> are more than or equals to half of number of <code>a</code>'s. To understand more clearly: In pattern an bm, first symbols <code>a</code> come then symbol <code>b</code>. total number of <code>a</code> 's is <code>n</code> and number of <code>b</code>'s is <code>m</code>. The inequality equation says about relation between <code>n</code> and <code>m</code>. To understand the equation: <pre><code>given: n <= 2m => n/2 <= m means `m` should be = or > then n/2 => numberOf(b) >= numberOf(a)/2 ...eq-1 </code></pre> So inequality of n and m says: <blockquote> numberOf(b) must be more then or equals to half of numberOf(a) </blockquote> Some example strings in L: <pre><code>b numberOf(a)=0 and numberOf(b)=1 this satisfy eq-1 bb numberOf(a)=0 and numberOf(b)=2 this satisfy eq-1 </code></pre> So in language string any number of <code>b</code> are possible without <code>a</code>'s. (any string of b) because any number is greater then zero (0/2 = 0). Other examples: <pre><code> m n -------------- ab numberOf(a)=1 and numberOf(b)=1 > 1/2 abb numberOf(a)=1 and numberOf(b)=2 > 1/2 abbb numberOf(a)=1 and numberOf(b)=3 > 1/2 aabb numberOf(a)=2 and numberOf(b)=2 > 2/2 = 1 aaabb numberOf(a)=3 and numberOf(b)=2 > 3/2 = 1.5 aaaabb numberOf(a)=4 and numberOf(b)=2 = 4/2 = 2 </code></pre> Points to be note: <ul> <li>all above strings are possible because number of <code>b</code>'s are either equal(=) to half of the number of <code>a</code> or more (>). </li> <li>and interesting point to notice is that total <code>a</code>'s can also be more then number of <code>b</code>'s, but not too much. Whereas number of <code>b</code>'s can be more then number of <code>a</code>'s by any number of times.</li> </ul> Two more important case are: <ul> <li>only <code>a</code> as a string not possible. </li> <li>note: null <code>^</code> string is also allowed because in <code>^</code> , <code>numberOf(a) = numberOf(b) = 0</code> that satisfy equation. </li> </ul> At once, it look that writing grammar is tough but really not... According to language description, we need following kinds of rules: rule 1: To generate <code>^</code> null string. <pre><code> N --> ^ </code></pre> rule 2: To generate any number of <code>b</code> <pre><code> B --> bB | b </code></pre> Rule 3: to generate <code>a</code>'s: (1) Remember you can't generate too many <code>a</code>'s without generating <code>b</code>'s. (2) Because <code>b</code>'s are more then = to half of <code>a</code>'s; you need to generate one <code>b</code> for every alternate <code>a</code> (3) Only <code>a</code> as a string not possible so for first (odd) alternative you need to add <code>b</code> with an <code>a</code> (4) Whereas for even alternative you can discard to add <code>b</code> (but not compulsory) So you overall grammar: <pre><code> S --> ^ | A | B B --> bB | b A --> aCB | aAB | ^ C --> aA | ^ </code></pre> here <code>S</code> is start Variable. In the above grammar rules you may have confusion in <code>A --> aCB | aAB | ^</code>, so below is my explanation: <pre><code>A --> aCB | aAB | ^ ^_____^ for second alternative a C --> aA <== to discard `b` and aAB to keep b </code></pre> let us we generate some strings in language using this grammar rules, I am writing Left most derivation to avoid explanation. <pre><code> ab S --> A --> aCB --> aB --> ab abb S --> A --> aCB --> aB --> abB --> abb abbb S --> A --> aCB --> aB --> abB --> abB --> abbB --> abbb aabb S --> A --> aAB --> aaABB --> aaBB --> aabB --> aabb aaabb S --> A --> aCB --> aaAB --> aaaABB --> aaaBB --> aaabB --> aaabb aaaabb S --> A --> aCB --> aaAB --> aaaCBB --> aaaaABB --> aaaaBB --> aaaabB --> aaaabb </code></pre> One more for non-member string: according to language a5 b2 = <code>aaaaabb</code> is not possible. because 2 >= 5/2 = 2.5 ==> 2 >= 2.5 inequality fails. So we can't generate this string using grammar too. I try to show below: In our grammar to generate extra <code>a</code>'s we have to use C variable. <pre><code>S --> A --> aCB --> aaAB --> aa aCB B --> aaa aA BB --> aaaa aCB BB --- ^ here with firth `a` I have to put a `b` too </code></pre> While my answer is done but I think you can change <code>A</code>'s rules like: <pre><code>A --> aCB | A | ^ </code></pre> Give it a Try!! EDIT: as @us2012 commented: It would seem to me that then, <code>S -> ^ | ab | aaSb | Sb</code> would be a simpler description. I feel this question would be good for OP and other also. OP's language: <blockquote> L = {an bm | n,m = 0,1,2,..., n <= 2m}. </blockquote> @us2012's Grammar: <pre><code>S -> ^ | ab | aaSb | Sb </code></pre> @us2012's question: <blockquote> Whether this grammar also generates language L? </blockquote> Answer is Yes! The inequality in language between number of <code>a</code>'s = <code>n</code> and number of <code>b</code> = m is <code>n =< 2m</code> We can also understand as: <pre><code> n =< 2m that is numberOf(a) = < twice of numberOf(b) </code></pre> And In grammar, when even we add one or two <code>a</code>'s we also add one <code>b</code> . So ultimately number of <code>a</code> can't be more then twice of number of <code>b</code>. Grammar also have rules to generate. any numbers of <code>b</code>'s and null <code>^</code> strings. So the simplified Grammar provided by @us2012 is CORRECT and also generates language L exactly. Notice: The first solution came from derivation as I written in am linked answer, I started with language description then tried to write some basic rules and progressively I could write complete grammar. Whereas @us2012 answer came by aptitude, you can gain the aptitude to write grammar by reading others solution and writing your for same..like you learn programming. 
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POConstruct grammar given the following language {a^n b^m | n,m = 0,1,2,...,n <= 2m}
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USCommunity
UserOwnerUserId
1. USGrijesh Chauhan
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. POConstruct grammar given the following language {a^n b^m | n,m = 0,1,2,...,n <= 2m}
 singulars
 PostTypePostTypeId
 PTQuestion
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTAcceptedByOriginator
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.